简介

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

排序算法的种类很多，例如选择排序，冒泡排序，插入排序，基数排序，快速排序，归并排序，堆排序，桶排序……

不同种类的排序算法用途一般不同，不过最常用的无非就是快速排序和sort函数排序，后者更是基本适用所有情况，接下来我要介绍的几种排序算法中也会着重介绍他们。

选择排序和冒泡排序

选择排序是一种十分直观的排序算法，大概就是在第i次循环中选中未排序元素中最小的元素，将其放到数组第i位，并进入下一轮寻找最小元素的循环中。

大致代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include"iostream"
using namespace std;
int main(){
	int n=4;
	int a[5]={1,5,4,9,3};
    //前n-1个元素排序完了，第n个元素就自动排序好了，并且这里数组下标从0开始，故循环至n-1
	for(int i=1;i<=n-1;i++){
		int mi=a[i],xb=i; //设置最小值和最小值元素对应下标 
		for(int j=i+1;j<=n;j++)
			if(a[j]<mi){
				mi=a[j];
				xb=j;
			}
		//交换元素 
		int tmp=a[i];
		a[i]=a[xb];
		a[xb]=tmp; 
	}
	for(int i=0;i<=n;i++)
		cout<<a[i]<<" ";
	return 0; 
}

这段代码运行结果如下：

1 3 4 5 9

可以看到，数组元素被正确排序了，尽管如此，选择排序并不是最符合我们要求的算法。

原因有二：

其一，不稳定性。选择排序的结果是对的，但是过程中数组元素并不是有序的，例如上述代码，最初数组元素为 1 5 4 9 3，第一轮排序，1是最小，数组元素相对大小顺序不会发生改变，但第二轮排序，3是最小，与5交换，数组元素变成1 3 4 9 5，5应该在9之前才是有序的，但在这里变成了5在9后面，打乱了未排序元素的相对大小顺序。

其二，糟糕的时间复杂度，可以看到，在代码中我们使用了两个循环，并且循环次数都可以近似看成n，也就是说，选择排序的时间复杂度是O(n²)，对于元素有几十万甚至更多的数组，排序时间是远远超出了限定时间的。

同样，冒泡排序的时间复杂度也是O(n²)，但它与选择排序不同的是，选择排序每轮寻找最小值，冒泡排序每轮寻找最大值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include"iostream"
using namespace std;
int main(){
	int n=4;
	int a[5]={1,5,4,9,3};
	//最外轮循环代表循环次数 
	for(int i=1;i<=n;i++){
		//如果有i-1个元素排序好了，后面i个元素就不用再遍历了 
		for(int j=1;j<=n-i;j++)
			//相邻元素比较大小交换 
			if(a[j]>a[j+1]){
				int tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
	}
	for(int i=0;i<=n;i++)
		cout<<a[i]<<" ";
	return 0; 
}

结果显然易见:1 3 4 5 9。

为什么叫冒泡排序呢？如果第一个元素最大，那他在第一轮排序与每个相邻元素都要交换，最后成为数组最后一位元素，这一轮排序全部操作列出来，第一个元素就像在逐渐沉底，那它反过来就是逐渐上升，像气泡逐渐上升冒出水面，故曰：冒泡排序。

选择排序具有不稳定性，但冒泡排序却具有稳定性，因为一定是比当前元素大的元素排在当前元素右边，原本相对大小顺序并不会改变。

快速排序

重头戏登场，没有时间为选择排序和冒泡排序的超时哀悼，随之赶到OJ的是——快速排序。

快速排序从两头同时排序，采用分治方法，最优情况下稳定的O(nlogn)时间复杂度简直薄纱上面两个排序算法，虽然最坏情况下时间复杂度仍是O(n²)，但在使用情况中基本不可能出现最坏情况，可以说它的时间复杂度就是O(nlogn)。

快排的思路就是：选中当前数组左端点i=l和右端点j=r以及分界点元素a[(l+r)/2]也就是最中间的元素，每次用while寻找i到中点的第一个大于分界点的元素，再用while循环寻找j到中点的第一个小于分界点的元素，如果i和j没有越过中点即i<=j，交换他们的值，排序完后，左端点到中点的元素都小于分界点，中点到右端点的元素都大于分界点，但是，他们这时还不是有序的，比如2 1 3 4 8 9 7，那怎么办呢？那还不简单，接着排序呗，这时排序就不用从最开始的左端点到右端点排序了，之前j–,如果j没有超过左端点l,那我们就可以把j作为右端点，同理如果i没有超过右端点r，i就可以作为新的左端点，调用自身，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void qsort(int a[],int l,int r){
	int i=l,j=r,mid=a[(i+j)/2];
	do{
		while(a[j]>mid) j--;
		while(a[i]<mid) i++;
		if(i<=j){
			int temp=a[j];
			a[j]=a[i];
			a[i]=temp;
			i++;
			j--;
		}
	}while(i<=j);
	if(i<r) qsort(a,i,r);
	if(l<j) qsort(a,l,j);
}

值得一提,qsort(num, n, sizeof(int), cmp)是stdlib.h头文件内的函数,也是c语言中唯二涉及算法的函数,另一个是二分，这里不讲喵。

sort函数排序

经典中的经典，algorithm头文件中自带的排序函数，适用范围极广，只要有排序的地方他就能排上用场，犹如亚里士多德般的全能感，令我的大脑旋转。

sort函数由快排和堆排优化实现，时间复杂度稳定在nlogn,使用起来十分方便，格式如下:

sort(begin, end, cmp)

总共有三个参数，前面两个分别代表待排序数组的开头和结尾，并不一定是0到n-1或者1到n，你可以做到数组中间排序而前后不排序，第三个参数是排序准则，这个参数可以把你自定义的函数加进去，比如说sort函数默认从小到大排序，如果你想要从大到小排序，可以自定义一个cmp函数，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
using namespace std;
//这里也可以是int类型 
bool cmp(int x,int y){
	return x>y;
}
int main(){
	//设置两个相同的数组 
	int a[5]={1,5,3,2,4};
	int b[5]={1,5,3,2,4};
	//a数组用原本的sort函数排序 
	sort(a,a+5);
	for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	//b数组用加了自定义函数的sort函数排序 
	sort(b,b+5,cmp);
	for(int i=0;i<5;i++)
		cout<<b[i]<<" ";
	return 0;
}

输出结果如下：

输出

可以看到，b数组实现了我们所要的从大到小排序。

sort函数对结构体排序

上面提到sort函数适用范围很广，对结构体也不例外，但结构体内包含多个变量，该如何进行排序呢？

很简单，我们照样自定义一个cmp函数，确定一个变量或者多个变量作为排序标准，这时候cmp函数的参数就是结构体了。

例如，我手上有一批学生的姓名，学号和成绩，我想把他们成绩从大到小排序，如果成绩相同，学号小的优先，那么，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
using namespace std;
struct student{
	//学号一般都是八位或者八位以上，用int可能会爆，用long long太占空间，所以用字符串表示 
	string name,xuehao;
	int score;
};
bool cmp(student x,student y){
	if(x.score!=y.score)
		return x.score>y.score;
	//字符串也是可以比较的，通过比较第一个不相同字符的字典序来判断大小 
	return x.xuehao<y.xuehao;
}
int main(){
	student a[4];
	//设置四个学生信息 
	a[0].name="dingbudele",a[0].xuehao="114515",a[0].score=750;
	a[1].name="ewoji",a[1].xuehao="114514",a[1].score=750;
	a[2].name="niganma",a[2].xuehao="114511",a[2].score=666;
	a[3].name="zhendeshinia",a[3].xuehao="114512",a[3].score=99;
	sort(a,a+4,cmp);
	for(int i=0;i<4;i++)
		cout<<a[i].name<<" "<<a[i].xuehao<<" "<<a[i].score<<endl;
	return 0;
}

输出结果如下：

结构体排序输出

可以看到成绩高的在前面，并且成绩相同时学号小的在前面喵，恭喜学号为114514的同学夺得第一，OVO。