排序问题

短命女 2022-12-03 08:47 134阅读 0赞

排序就是将数据按一定顺序重新排列。它是许多算法的基础，可以让数据变得更容易处理。本篇将整理一些相对基础的排序算法。  
以下算法都是以解答例题的形式说明。例题：将给出的一串数字按照从小到大的顺序排，在第1行输入定义数组长度的整数N（N<10000)，在第2行输入N个整数，以空格隔开，输出N个整数。  
例如输入：1 5 3 4 7 9 8  
输出：1 3 4 5 7 8 9

## 插入排序法 ##

**要点：**  
1.取出未排序部分的开头元素赋给变量v  
2.在已排序部分，将所有比v大的元素向后移动一个单位  
3.将以取出的元素v插入空位  
**代码**

#include<iostream>
    using namespace std;
    const int MAXN = 10000;
    int a[MAXN];
    void insertion(int N){
        
    	for(int i = 1;i < N;i++){
        
    		int v = a[i];
    		int j = i - 1;
    		while(j >= 0 && a[j] > v){
        
    			a[j+1] = a[j];
    			j--;
    		}
    		a[j+1] = v;
    	}
    }
    int main(){
        
    	int N;
    	cin>>N;
    	for(int i = 0;i < N;i++){
        
    		cin>>a[i];
    	} 
    	insertion(N);
    	for(int i = 0;i < N;i++){
        
    		cout<<a[i]<<" ";
    	}
    	return 0;
    }

**分析**  
在插入排序法中，我们只将比v（取出的值）大的元素向后平移，不相邻的元素不会直接交换位置，因此**整个排序算法十分稳定**  
插入排序法是一种很有趣的算法，输入数据的顺序能大幅影响它的复杂度。我们计算出它的复杂度为O(N^2)，也仅是指输入数据为降序排列的情况。如果输入数据为升序排列，那么A\[j\]从头至尾都不需要移动，程序只需要经历N次比较便可执行完毕。**可见，插入排序的优势就在于能快速处理相对有序的数据。**

## 冒泡排序法 ##

**要点**  
1.从数组末尾开始依次比较相邻两个元素，如果大小关系相反则交换位置  
**代码**

#include<iostream>
    using namespace std;
    const int MAXN = 10000;
    int a[MAXN];
    void insertion(int N){
        
    	for(int k = 0;k < N;++k){
        
    		for(int i = N - 1;i > 0;i--){
        
    		int j = i - 1;
    			if(a[j] > a[i]){
        
    				int temp = a[j];		//交换 
    				a[j] = a[i];
    				a[i] = temp;
    			}
    		
    		}
    	}	
    }
    int main(){
        
    	int N;
    	cin>>N;
    	for(int i = 0;i < N;i++){
        
    		cin>>a[i];
    	} 
    	insertion(N);
    	for(int i = 0;i < N;i++){
        
    		cout<<a[i]<<" ";
    	}
    	return 0;
    }

从代码中很容易能看出，**程序每完成一次外层循环，已排序部分就会增加一个元素**。这样一来，程序外层循环最多需要执行N次，同时内层循环的处理范围也会逐渐减小。因此，我们可以发挥外层循环变量i的作用，对冒泡排序的算法作一些修改。  
修改后的代码(insertion函数)：

void insertion(int N){
        
    	bool flag = true;
    	int i = 0;
    	while(flag == true){
        
    		flag = false;
    		for(int j = N - 1;j >= i;j--){
        
    			if(a[j] < a[j-1]){
        
    				int temp = a[j-1];		//交换 
    				a[j-1] = a[j];
    				a[j] = temp;
    				flag = true;
    			}
    		}
    	}
    }

flag用来表示当前数组是否还需要进行排序  
**分析**  
冒泡排序法仅对数组中的相邻元素进行比较和交换，因此键相同的元素不会改变顺序。所以冒泡排序法也属于一种稳定排序的算法。其算法复杂度为O(N^2)

## 选择排序法 ##

**要点**  
1.找出未排序部分最小值的位置minj  
2.将minj位置的元素与未排序部分的起始元素交换  
**代码**

#include<iostream>
    using namespace std;
    const int MAXN = 10000;
    int a[MAXN];
    void insertion(int N){
        
    	for(int i = 0;i < N - 1;i++){
        
    		int minj = i;
    		for(int j = i;j < N;j++){
        
    			if(a[minj] > a[j]){
        
    				minj = j;		//记录最小值的位置 
    			}
    		}
    		int temp = a[minj];
    		a[minj] = a[i];
    		a[i] = temp;
    	}
    }
    int main(){
        
    	int N;
    	cin>>N;
    	for(int i = 0;i < N;i++){
        
    		cin>>a[i];
    	} 
    	insertion(N);
    	for(int i = 0;i < N;i++){
        
    		cout<<a[i]<<" ";
    	}
    	return 0;
    }

**分析**  
由于选择排序法会直接交换两个不相邻的元素，所以属于不稳定的排序算法。并且该算法的复杂度为O(N^2)

## 总结 ##

比较一下以上三种排序算法：  
冒泡排序法与选择排序法相比，一个从局部入手减少逆序元素，一个放眼大局逐个选择最小值，二者思路不大相同。但是，它们又都有着“**通过i次外层循环，从数据中顺次求出i个最小值**”的相同特征。相对地，插入排序法是通过i次外层循环，直接将原数组地i个元素重新排序。另外，不含flag的简单冒泡排序法和选择排序法不依赖数据，即比较运算的次数（算法复杂度）不受输入数据的影响，而插入算法在执行时却依赖数据，处理某些数据时具有很高的效率。

## 希尔排序法 ##

**要点**  
1.在插入排序法的基础上进一步扩展，程序会重复进行以间隔为g的元素为对象的插入排序。  
**代码**

#include<iostream>
    #include<vector>
    using namespace std;
    const int MAXN = 10000;
    int a[MAXN];
    vector<int> p;			//p数组用来存放排序间隔 
    void insertion(int N,int g){
        
    	for(int i = g;i < N;i++){
        
    		int v = a[i];
    		int j = i - g;
    		while(j >= 0 && a[j] > v){
        
    			a[j+g] = a[j];
    			j -= g;
    		}
    		a[j+g] = v;
    	}
    }
    
    
    void shell(int N){
        
    	//首先求出排序间隔,并存放到p中 
    	for(int i = 1;i < N;i = i*3 + 1){
        
    		p.push_back(i);
    	}
    	//从大间隔到小间隔开始排序 
    	for(int i = p.size() - 1;i >= 0;i--)
    		insertion(N,p[i]); 
    }
    int main(){
        
    	int N;
    	cin>>N;
    	for(int i = 0;i < N;i++){
        
    		cin>>a[i];
    	} 
    	shell(N);
    	for(int i = 0;i < N;i++){
        
    		cout<<a[i]<<" ";
    	}
    	return 0;
    }

**分析**  
当分隔间断为1，4，13，40，121…，即Gn+1 = 3Gn + 1时，算法的复杂段基本维持在O(N^1.25)