Fork me on GitHub

排序算法总结

发表于   |     |   阅读次数

这是《大话数据结构》第九章排序算法的知识点总结。

排序的基本概念与分类

假设含有n个记录的序列为${r_1,r_2,\cdots,r_n}$，其相应的关键字分别为${k_1,k_2,\cdots,k_n}$，需要确定$1,2, \cdots, n$的一种排列$p_1,p_2,\cdots,p_n$，使其相应的关键字满足$k_{p1}\le k_{p2}\le \cdots \le k_{pn}$非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列${r_{p1}, r_{p2}, \cdots, r_{pn}}$，这样的操作就称为排序。

在排序问题中，通常将数据元素称为记录。

排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。

这里关键字$k_i$可以是记录$r$的主关键字，也可以是次关键字，甚至是若干数据项的组合。

排序的稳定性

由于排序不仅是针对主关键字，还有针对次关键字，因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能会存在不唯一的情况，下面给出稳定与不稳定排序的定义。

假设$k_i = k_j \ (1\le i \le n, 1\le j\le n, i\neq j)$，且在排序前的序列中$r_i$领先于$r_j$（即$i \lt j$）。如果排序后$r_i$仍领先于$r_j$，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中$r_j$领先于$r_i$，则称所用的排序方法是不稳定的。

不稳定的排序算法有：希尔、快速、堆排和选择排序。

内排序和外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序可以分为：内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序来说，排序算法的性能主要是受到3个方面的影响：

时间性能

在内排序中，主要进行两种操作：比较和移动。高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

辅助空间

辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

算法的复杂性

这里指的是算法本身的复杂度，而不是算法的时间复杂度。

根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。

排序用到的结构与函数

这里先提供一个用于排序用的顺序表结构，这个结构将用于接下来介绍的所有排序算法。

1
2
3
4
5
6
7
8
#define MAXSIZE 10
typedef struct
{
  // 用于存储待排序数组
  int r[MAXSIZE]; 
  // 用于记录顺序表的长度
  int length;
}SqList;

此外，由于排序最常用到的操作是数组两元素的交换，这里写成一个函数，如下所示：

1
2
3
4
5
6
// 交换L中数组r的下标为i和j的值
void swap(SqList *L, int i, int j){
  int temp = L->r[i];
  L->r[i] = L->r[j];
  L->r[j] = temp;
}

冒泡排序

冒泡排序(Bubble sort)是一种交换排序。它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

首先介绍一个简单版本的冒泡排序算法的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
// 冒泡排序初级版
void BubbleSort0(SqList *L){
	int i, j;
	for (i = 0; i < L->length - 1; i++) {
		for (j = i + 1; j <= L->length - 1; j++){
			if (L->r[i] > L->r[j]){
				// 实现递增排序
				swap(L, i, j);
			}
		}
	}
}

这段代码不算是标准的冒泡排序算法，因为不满足“两两比较相邻记录”的冒泡排序思想，它更应该是最简单的交换排序。它的思路是让每一个关键字都和后面的每一个关键字比较，如果大或小则进行交换，这样关键字在一次循环后，第一个位置的关键字会变成最大值或者最小值。

这个最简单的实现算法效率是非常低的。

下面介绍正宗的冒泡排序算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 正宗的冒泡排序算法实现代码
void BubbleSort(SqList *L){
	int i, j;
	for (i = 0; i < L->length; i++) {
		for (j = L->length - 2; j >= i; j--){
			// j是从后往前循环
			if (L->r[j] > L->r[j + 1]){
				// 实现递增排序
				swap(L, j, j + 1);
			}
		}
	}
}

这里改变的地方是在内循环中，j是从数组最后往前进行比较，并且是逐个往前进行相邻记录的比较，这样最大值或者最小值会在第一次循环过后，从后面浮现到第一个位置，如同气泡一样浮到上面。

这段实现代码其实还是可以进行优化的，例如待排序数组是{2,1,3,4,5,6,7,8,9},需要进行递增排序，可以发现其实只需要交换前两个元素的位置即可完成，但是上述算法还是会在交换完这两者位置后继续进行循环，这样效率就不高了，所以可以在算法中增加一个标志，当有一次循环中没有进行数据交换，就证明数组已经是完成排序的，此时就可以退出算法，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 改进版冒泡算法
void BubbleSortOptimz(SqList *L){
	int i, j;
	bool flag = true;
	for (int i = 0; i < L->length && flag; i++){
		// 若 flag为false则退出循环
		flag = false;
		for (j = L->length - 2; j >= i; j--){
			// j是从后往前循环
			if (L->r[j] > L->r[j + 1]){
				// 实现递增排序
				swap(L, j, j + 1);
				// 如果有数据交换，则flag是true
				flag = true;
			}
		}
	}
}

冒泡排序算法的时间复杂度是$O(n^2)$。

完整的冒泡排序算法代码可以查看BubbleSort。

简单选择排序

简单选择排序算法(Simple Selection Sort)就是通过$n-i$次关键字间的比较，从$n-i+1$个记录中选出关键字中最小的记录，并和第$i(1\le i \le n)$个记录进行交换。

下面是实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 简单选择排序算法
void SelectSort(SqList *L){
	int i, j, min;
	for (i = 0; i < L->length - 1; i++){
		// 将当前下标定义为最小值下标
		min = i;
		for (j = i + 1; j <= L->length - 1; j++){
			if (L->r[j] < L->r[min])
				min = j;
		}
		// 若min不等于i，说明找到最小值，进行交换
		if (min != i)
			swap(L, i, min);
	}
}

简单选择排序的最大特点就是交换移动数据次数相当少。分析其时间复杂度发现，无论最好最差的情况，比较次数都是一样的，都需要比较$\sum_{i=1}^{n-1} (n-i) = (n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2}$次。对于交换次数，最好的时候是交换0次，而最差的情况是$n-1$次。因此，总的时间复杂度是$O(n^2)$，虽然与冒泡排序一样的时间复杂度，但是其性能上还是略好于冒泡排序。

直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 直接插入排序
void InsertSort(SqList *L){
	int i, j,val;
	for (i = 1; i <= L->length - 1; i++){
		if (L->r[i] < L->r[i - 1]){
			// 将L->r[i]插入有序表中,使用val保存待插入的数组元素L->r[i]
			val = L->r[i];
			for (j = i - 1; L->r[j]>val; j--)
				// 记录后移
				L->r[j + 1] = L->r[j];	
			// 插入到正确位置
			L->r[j + 1] =val;
		}
	}
}

直接插入排序算法是需要有一个保存待插入数值的辅助空间。

在时间复杂度方面，最好的情况是待排序的表本身就是有序的，如{2,3,4,5,6}，比较次数则是$n-1$次，然后不需要进行移动，时间复杂度是$O(n)$。

最差的情况就是待排序表是逆序的情况，如{6,5,4,3,2},此时需要比较$\sum_{i=2}^{n} i = \frac{(n+2)(n-1)}{2}$次，而记录的移动次数也达到最大值$\sum_{i=2}^{n} (i+1) = \frac{(n+4)(n-1)}{2}$次。

如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为$\frac{n^2}{4}$。因此，可以得出直接插入排序算法的时间复杂度是$O(n^2)$。同时也可以看出，直接插入排序算法会比冒泡排序和简单选择排序算法的性能要更好一些。

希尔排序

上述三种排序算法的时间复杂度都是$O(n^2)$，而希尔排序是突破这个时间复杂度的第一批算法之一。

其实直接插入排序的效率在某些情况下是非常高效的，这些情况是指记录本来就很少或者待排序的表基本有序的情况，但是这两种情况都是特殊情况，在现实中比较少见。而希尔排序就是通过创造条件来改进直接插入排序的算法。

希尔排序的做法是将原本有大量记录数的记录进行分组，分割成若干个序列，这样每个子序列待排序的记录就比较少了，然后就可以对子序列分别进行直接插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序。

这里的基本有序是指小的关键字基本在前面，大的基本在后面，不大不小的在中间。像{2,1,3,6,4,7,5,8,9}可以称为基本有序。

这里的关键就是如何进行分割，希尔排序采取的是跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 希尔排序
void ShellSort(SqList *L){
	int i, j,val;
	int increment = L->length;
	do{
		// 增量序列
		increment = increment / 3 + 1;
		for (i = increment; i <= L->length - 1; i++){
			if (L->r[i]<L->r[i - increment]){
				// 将L->r[i]插入有序表中,使用val保存待插入的数组元素L->r[i]
				val = L->r[i];
				for (j = i - increment; j >= 0 && L->r[j]>val; j -= increment)
					// 记录后移，查找插入位置
					L->r[j + increment] = L->r[j];
				L->r[j + increment] = val;
			}
		}
	} while (increment > 1);
}

上述代码中增量的选取是increment = increment / 3 + 1，实际上增量的选取是非常关键的，现在还没有人找到一种最好的增量序列，但是大量研究表明，当增量序列是$\delta [k] = 2^{t-k+1} - 1 (0\le k \le t \le \lfloor log_2(n+1)\rfloor)$时，可以获得不错的效率，其时间复杂度是$O(n^{\frac{3}{2}})$，要好于直接插入排序的$O(n^2)$。当然，这里需要注意的是增量序列的最后一个增量值必须等于1才行。此外，由于记录是跳跃式的移动，希尔排序是不稳定的排序算法。

桶排序

有一个数量为Size个数的数组A，数组的值范围为(0 - Max)，然后创建一个大小为Max+1的数组B，每个元素都为0.从头遍历A，当读取到A[i]的时候，B[A[i]]的值+1，这样所有的A数组被遍历后，直接扫描B之后，输出表B就可以了。然后再根据B来对A进行排序。

实现代码如下：

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
27
28
29
30
31
32
33
34
35
36
37
//获得未排序数组中最大的一个元素值
int GetMaxVal(int* arr, int len)
{
	int maxVal = arr[0]; //假设最大为arr[0]
	for (int i = 1; i < len; i++)  //遍历比较，找到大的就赋值给maxVal
	{
		if (arr[i] > maxVal)
			maxVal = arr[i];
	}
	return maxVal;  //返回最大值
}
void BucketSort(int *numbers, int length){
	if (numbers == NULL || length <= 0){
		cout << "wrong input!";
		return;
	}
	int size = GetMaxVal(numbers,length) + 1;
	vector<int> bucket(size);
	for (int i = 0; i < length + 1; i++){
		bucket[i] = 0;
	}
	// 计算数组中每个元素出现的次数
	for (int i = 0; i < length; i++){
		int j = numbers[i];
		bucket[j] += 1;
	}
	// 排序
	int count = 0;
	for (int i = 0; i < size; i++){
		if (bucket[i] > 0){
			for (int j = 0; j < bucket[i]; j++){
				numbers[count] = i;
				count++;
			}
		}
	}
}

堆排序

简单选择排序在待排序的$n$个记录中选择一个最小的记录需要比较$n-1$次，这是查找第一个数据，所以需要比较这么多次是比较正常的，但是可惜的是它没有把每一趟的比较结果保存下来，这导致在后面的比较中，实际有许多比较在前一趟中已经做过了。因此，如果可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会变得很高了。

堆排序(Heap Sort)就是对简单选择排序进行的一种改进，并且效果非常明显。

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为最大堆或者大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为最小堆或者小顶堆。

下图是一个例子，左边的是大顶堆，而右边的是小顶堆。

而根据堆的定义，可以知道根结点一定是堆中所有结点最大或者最小者。如果按照层遍历的方式给结点从1开始编号，则结点之间满足下列关系：

如果将上图按照层遍历存入数组，则一定满足上述关系表达，得到的数组如下图所示。

堆排序的基本思想是，将待排序的序列构成一个最大堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的$n-1$个序列重新构成一个堆，这样就会得到$n$个元素中的次最大值。如此反复执行，便能得到一个有序序列。

下面将给出堆排序算法的代码实现。

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
27
28
29
30
31
32
33
34
35
// 已知L->r[s...m]中记录的关键字除L->r[s]之外均满足堆的定义
// 本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆
void HeapAdjust(SqList *L, int s, int m){
	int temp, j;
	temp = L->r[s];
	for (j = 2 * s; j <= m - 1; j *= 2){
		// 沿关键字较大的孩子结点向下筛选
		if (j < m-1 && L->r[j] < L->r[j + 1])
			// j是关键字中较大的记录的下标
			++j;
		if (temp >= L->r[j])
			// 当前值不需要进行调整
			break;
		L->r[s] = L->r[j];
		s = j;
	}
	// 插入
	L->r[s] = temp;
}

// 堆排序
void HeapSort(SqList *L){
	int i;
	for (i = L->length / 2; i >= 0; i--){
		// 将待排序的序列构成一个最大堆
		HeapAdjust(L, i, L->length);
	}
	// 开始进行排序
	for (i = L->length - 1; i > 0; i--){
		// 将堆顶记录与当前未经排序的子序列的最后一个记录交换
		swap(L, 0, i);
		// 重新调整为最大堆
		HeapAdjust(L, 0, i - 1);
	}
}

从代码中可以看出，堆排序分两步走，首先是将待排序的序列构造成最大堆，这也是HeapSort()中第一个循环所做的事情，第二个循环也就是第二步，进行堆排序，逐步将每个最大值的根结点和末尾元素进行交换，然后再调整成最大堆，重复执行。

而在第一步中构造最大堆的过程中，是从$\lfloor \frac{n}{2} \rfloor$的位置开始进行构造，这是从下往上、从右到左，将每个非叶结点当作根结点，将其和其子树调整成最大堆。

接下来就是分享堆排序的效率了。堆排序的运行时间主要是消耗在初始构造堆和在重建堆时的反复筛选上。

在构建堆的过程中，因为是从完全二叉树的最下层最右边的非叶结点开始构建，将它与其孩子进行比较和若有必要的交换，对每个非叶结点，最多进行两次比较和互换操作，这里需要进行这种操作的非叶结点数目是$\lfloor \frac{n}{2} \rfloor$个，所以整个构建堆的时间复杂度是$O(n)$。

在正式排序的时候，第$i$取堆顶记录重建堆需要用$O(log i)$的时间(完全二叉树的某个结点到根结点的距离是$\lfloor log_2i \rfloor + 1$)，并且需要取$n-1$次堆顶记录，因此，重建堆的时间复杂度是$O(nlogn)$。

所以，总体上来说，堆排序的时间复杂度是$O(nlogn)$。由于堆排序对原始记录的排序状态并不敏感，因此它无论最好、最坏和平均时间复杂度都是$O(nlogn)$。同样由于记录的比较与交换是跳跃式进行，堆排序也不是稳定的排序算法。

另外，由于初始构建堆需要的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

归并排序

归并排序(Merging Sort)就是利用归并的思想实现的排序方法，它的原理是假设初始序列有$n$个记录，则可以看成是$n$个有序的子序列，每个子序列的长度为1，然后两两合并，得到$\lceil \frac{n}{2} \rceil$($\lceil x \rceil$表示不小于$x$的最小整数)个长度为2或1的有序子序列；再两两合并，$\cdots \cdots$，如此重复，直至得到一个长度为$n$的有序序列为止，这种排序方法称为2路归并排序。

下面是介绍实现的代码。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 归并排序,使用递归
void MergeSort(SqList *L){
	MSort(L->r, L ->r, 0, L->length-1);
}
// 将SR[s..t]归并排序为TR1[s..t]
void MSort(int SR[], int TR1[], int s, int t){
	int m;
	int TR2[MAXSIZE];
	if (s == t)
		TR1[s] = SR[s];
	else{
		// 将SR[s..t]平分为SR[s...m-1]和SR[m...t]
		m = (s + t) / 2+1;
		MSort(SR, TR2, s, m-1);
		MSort(SR, TR2, m, t);
		// 将TR2[s..m-1]和TR2[m..t]归并到TR1[s..t]
		Merge(TR2, TR1, s, m-1, t);
	}
}
// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Merge(int SR[], int TR[], int i, int m, int n){
	int j, k, l;
	for (j = m+1, k = i; i <= m && j <= n; k++){
		// 将SR中记录由小到大并入TR
		if (SR[i] < SR[j])
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	}
	if (i <= m){
		for (l = 0; l <= m - i; l++)
			// 将剩余的SR[i..m]复制到TR
			TR[k + l] = SR[i + l];
	}
	if (j <= n){
		for (l = 0; l <= n - j; l++)
			// 将剩余的SR[j..n-1]复制到TR
			TR[k + l] = SR[j + l];
	}
}

上述代码是一个递归版本的归并排序实现算法，其中函数MSort()的作用是将待排序序列进行分割，然后Merge()函数会对需要归并的序列进行排序并两两归并在一起。

归并排序的时间复杂度是$O(nlogn)$，并且无论是最好、最坏还是平均都是同样的时间性能。另外，在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果，并且递归时需要深度为$log_2 n$的栈空间，因此空间复杂度是$O(n+logn)$。

另外，归并排序是使用两两比较，不存在跳跃，这在Merge()中的语句if(SR[i]<SR[j])可以看出，所以归并排序是一个稳定的排序算法。

总体来说，归并排序是一个比较占用内存，但效率高且稳定的算法。

下面会介绍一个非递归版本的归并排序算法实现。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 非递归版本的归并排序
void MergeSort2(SqList *L){
	// 申请额外空间
	int* TR = (int *)malloc(L->length * sizeof(int));
	int k = 1;
	while (k < L->length){
		MergePass(L->r, TR, k, L->length);
		// 子序列长度加倍
		k = 2 * k;
		MergePass(TR, L->r, k, L->length);
		k = 2 * k;
	}
}
// 将SR[]中相邻长度为s的子序列两两归并到TR[]
void MergePass(int SR[], int TR[], int s, int n){
	int i = 0;
	int j;
	while (i <= n - 2 * s){
		// 两两归并
		Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
		i = i + 2 * s;
	}
	if (i < n - s + 1)
		// 归并最后两个子序列
		Merge(SR, TR, i, i + s - 1, n - 1);
	else{
		// 若最后剩下单个子序列
		for (j = i; j <= n - 1; j++)
			TR[j] = SR[j];
	}
}
// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Merge(int SR[], int TR[], int i, int m, int n){
	int j, k, l;
	for (j = m+1, k = i; i <= m && j <= n; k++){
		// 将SR中记录由小到大并入TR
		if (SR[i] < SR[j])
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	}
	if (i <= m){
		for (l = 0; l <= m - i; l++)
			// 将剩余的SR[i..m]复制到TR
			TR[k + l] = SR[i + l];
	}
	if (j <= n){
		for (l = 0; l <= n - j; l++)
			// 将剩余的SR[j..n-1]复制到TR
			TR[k + l] = SR[j + l];
	}
}

非递归版本的归并排序算法避免了递归时深度为$log_2 n$的栈空间，空间复杂度是$O(n)$，并且避免递归也在时间性能上有一定的提升。应该说，使用归并排序时，尽量考虑用非递归方法。

快速排序

在前面介绍的几种排序算法，希尔排序相当于直接插入排序的升级，它们属于插入排序类，而堆排序相当于简单选择排序的升级，它们是属于选择排序类，而接下来介绍的快速排序就是冒泡排序的升级，它们属于交换排序类。

快速排序(Quick Sort)的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

下面给出实现的快速排序算法代码：

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
27
28
29
30
31
32
33
34
// 快速排序
void QuickSort(SqList *L){
	QSort(L, 0, L->length - 1);
}
// 对待排序序列L中的子序列L->r[low...high]做快速排序
void QSort(SqList *L, int low, int high){
	int pivot;
	if (low < high){
		// 将L->r[low...high]一分为二，算出枢轴值pivot
		pivot = Partition(L, low, high);
		// 对低子序列递归排序
		QSort(L, low, pivot - 1);
		// 对高子序列递归排序
		QSort(L, pivot + 1, high);
	}
}
// 交换待排序序列L中子表的记录，使枢轴记录到位，并返回其所在位置
// 并使得其之前位置的值小于它，后面位置的值大于它
int Partition(SqList *L, int low, int high){
	int pivot_key;
	// 初始值设置为子表的第一个记录
	pivot_key = L->r[low];
	while (low < high){
		while (low < high && L->r[high] >= pivot_key)
			high--;
		// 将小于枢轴记录的值交换到低端
		swap(L, low, high);
		while (low < high && L->r[low] <= pivot_key)
			low++;
		// 将大于枢轴记录的值交换到高端
		swap(L, low, high);
	}
	return low;
}

上述代码同样是使用了递归，其中Partition()函数要做的就是先选取待排序序列中的一个关键字，然后将其放在一个位置，这个位置左边的值小于它，右边的值都大于它，这样的值被称为枢轴。

快速排序的时间性能取决于快速排序递归的深度。在最优情况下，Partition()每次都划分得很均匀，如果排序$n$个关键字，其递归树的深度技术$\lfloor log_ n \rfloor +1$，即需要递归$log_2n$次，其时间复杂度是$O(nlogn)$。而最坏的情况下，待排序的序列是正序或逆序，得到的递归树是斜树，最终其时间复杂度是$O(n^2)$。

平均情况可以得到时间复杂度是$O(nlogn)$，而空间复杂度的平均情况是$O(logn)$。但是由于关键字的比较和交换是跳跃进行的，所以快速排序也是不稳定排序。

快速排序的优化

快速排序算法是有许多地方可以优化的，下面给出一些优化的方案。

优化选取枢轴

枢轴的值太大或者太小都会影响快速排序的性能，一个改进方法是三数取中法，即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数。

需要在Partition()函数中做出下列修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pivot_key;
	// 使用三数取中法选取枢轴
	int m = low + (high - low) / 2;
	if (L->r[low] > L->r[high])
		// 保证左端最小
		swap(L, low, high);
	if (L->r[m] > L->r[high])
		// 保证中间较小
		swap(L, high, m);
	if (L->r[m] > L->r[low])
		// 保证左端较小
		swap(L, m, low);

	pivot_key = L->r[low];

三数取中对小数组有很大的概率取到一个比较好的枢轴值，但是对于非常大的待排序的序列还是不足以保证得到一个比较好的枢轴值，因此还有一个办法是九数取中法，它先从数组中分三次取样，每次去三个数，三个样品各自取出中数，然后从这三个中数当中再取出一个中数作为枢轴。

优化不必要的交换

优化后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pivot_key = L->r[low];
int temp = pivot_key;
while (low < high){
	while (low < high && L->r[high] >= pivot_key)
		high--;
	// 将小于枢轴记录的值交换到低端
	// swap(L, low, high);
	// 采用替换而不是交换的方式进行操作
	L->r[low] = L->r[high];
	while (low < high && L->r[low] <= pivot_key)
		low++;
	// 将大于枢轴记录的值交换到高端
	// swap(L, low, high);
	// 采用替换而不是交换的方式进行操作
	L->r[high] = L->r[low];
}
// 将枢轴值替换回L.r[low]
L->r[low] = temp;
return low;

这里可以减少多次交换数据的操作，性能上可以得到一定的提高。

优化小数组时的排序方案

当数组比较小的时候，快速排序的性能其实还不如直接插入排序(直接插入排序是简单排序中性能最好的)。其原因是快速排序使用了递归操作，在有大量数据排序时，递归操作的影响是可以忽略的，但如果只有少数记录需要排序，这个影响就比较大，所以下面给出改进的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAX_LENGTH_INSERT_SORT 7 
// 对待排序序列L中的子序列L->r[low...high]做快速排序
void QSort(SqList *L, int low, int high){
	int pivot;

	if ((high - low) > MAX_LENGTH_INSERT_SORT){
		// 当high - low 大于常数时用快速排序
		// 将L->r[low...high]一分为二，算出枢轴值pivot
		pivot = Partition(L, low, high);
		// 对低子序列递归排序
		QSort(L, low, pivot - 1);
		// 对高子序列递归排序
		QSort(L, pivot + 1, high);
	}
	else{
		// 否则使用直接插入排序
		InsertSort(L);
	}
}

上述代码是先进行一个判断，当数组的数量大于一个预设定的常数时，才进行快速排序，否则就进行直接插入排序。这样可以保证最大化地利用两种排序的优势来完成排序工作。

优化递归操作

递归对性能是有一定影响的，QSort()在其尾部有两次递归操作，如果待排序的序列划分极端不平衡，递归的深度将趋近于$n$，而不是平衡时的$log_2 n$，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此，如果能减少递归，将会大大提高性能。

下面给出对QSort()实施尾递归优化的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 对待排序序列L中的子序列L->r[low...high]做快速排序
void QSort(SqList *L, int low, int high){
	int pivot;

	if ((high - low) > MAX_LENGTH_INSERT_SORT){
		// 当high - low 大于常数时用快速排序
		while (low < high){
			// 将L->r[low...high]一分为二，算出枢轴值pivot
			pivot = Partition(L, low, high);
			// 对低子序列递归排序
			QSort(L, low, pivot - 1);
			// 尾递归
			low = pivot + 1;
		}
	}
	else{
		// 否则使用直接插入排序
		InsertSort(L);
	}
}

上述代码中使用while循环，并且去掉原来的对高子序列进行递归，改成代码low = privot + 1，那么在进行一次递归后，再进行循环，就相当于原来的QSort(L,privot+1,high);，结果相同，但是从递归变成了迭代，可以缩减堆栈深度，从而提高了整体性能。

总结

上述总共介绍了7种排序算法，首先是根据排序过程中借助的主要操作，将内排序分为：插入排序、交换排序、选择排序和归并排序，如下图所示。

事实上，目前还没有十全十美的排序算法，都是各有优点和缺点，即使是快速排序算法，也只是整体上性能优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。

下面对这7种算法的各种指标进行对比，如下图所示：

从算法的简单性来看，可以分为两类：

  • 简单算法：冒泡、简单选择、直接插入。
  • 改进算法：快速、堆、希尔、归并。

从平均情况看，快速、堆、归并三种改进算法都优于希尔排序，并远远胜过3种简单算法。

从最好情况看，冒泡和直接插入排序要更好一点，即当待排序序列是基本有序的时候，应该考虑这两种排序算法，而非4种复杂的改进算法。

从最坏情况看，堆和归并排序比其他排序算法都要更好。

从空间复杂度看，归并排序和快速排序都对空间有要求，而其他排序反而都只是$O(1)$的复杂度。

从稳定性上看，归并排序是改进算法中唯一稳定的算法。而不稳定的排序算法有“快些选堆”，即快速、希尔、选择和堆排序四种算法（书中给出的简单选择排序是不稳定的，但是从网上查找资料看到选择排序是一个不稳定的算法）。

排序算法的总结就到这里，实际上还是要根据实际问题来选择适合的排序算法。

全部排序算法的代码可以查看排序算法实现代码。