基本排序算法

小灰灰 2022-05-31 08:56 117阅读 0赞

1.冒泡排序：  
排序基本思想：  
一个一个的比较，将最大或者最小的数冒到最后面；  
是稳定算法  
算法时间复杂度：大于 n ^ 2;

// 默认从小到大
    void MySort(int num[], int len){
    	int temp = 0;
    	for(int i = 0; i < len - 1; i++){
    		for(int j = 0; j < len - i - 1; j++){
    			if(num[i] > num[j]){
    				temp = num[i]; 
    				num[i] = num[j]; 
    				num[j] = temp;
    			}
    		}
    	}
    }

1.选择排序：  
排序基本思想：  
一个一个的比较，将最大或者最小的数冒到最前面；  
算法时间复杂度： n ^ 2; 由于交换次数比较少（一般快冒泡6倍）  
是稳定算法

// 默认从小到大
    void MySort(int num[], int len){	
    	int index = -1;
    	int temp = 0;
    	for(int i = 0; i < len - 1; i++){
    		temp = num[i];
    		index = i;
    		for(int j = i + 1; j < len; j++){
    			if(num[i] > num[j]){
    				// 记录要交换的数的下标 但不交换
    				index = j;
    				temp = num[j];
    			}
    		}
    		num[index] = num[i];
    		num[i] = temp;
    	}
    }

1.插入排序：  
排序基本思想：  
基于有序数列的排序，将大于（小于）的数插入到对应位置；  
算法时间复杂度： n ^ 2;  
是稳定算法  
（略微优于冒泡）在特定情况下用非常好；比如输入时进行插入排序就会有非常好的效果

// 默认从小到大
    void MySort(int num[], int len){
    	int temp = 0;
    	int index = -1;
    	for(int i = 1; i < len; i++){
    		int temp = num[i];// 哨兵记录当前排序的数,防止丢失
    		index = i;
    		// 从待排序的前面一个数开始
    		int j = index - 1;
    		for(; j >= 0 && num[j] > temp; j--){
    		// 把不符合的数向后移动, 有哨兵不怕数据丢失
    			num[j + 1] = num[j];
    		}
    		// 插入在应插入的位置
    		num[j+1] = temp;
    	}
    }