数据结构第十章：排序

Posted on | In , | |

Abstract：排序。

排序初导

排序：使序列成为一个按关键字有序的序列。

排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。

若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。

排序分为两类：内排序和外排序。

  • 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。在排序整个过程中，待排序的所有记录全部被放置在内存中。
  • 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

基本概念和分类：

  • 在排序问题中，通常将数据元素称为记录
  • 排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。
  • 关键字kiki可以是记录rr的主关键字，也可以是次关键字，甚至是若干数据项的组合。

排序的稳定性：

  • 定义：假设ki=kj (1≤i≤n,1≤j≤n,i≠j)ki=kj (1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中riri领先于rjrj（即i<ji<j）。如果排序后riri仍领先于rjrj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rjrj领先于riri，则称所用的排序方法是不稳定的。
  • 不稳定的排序算法有：希尔、快速、堆排和选择排序。

时间性能：

  • 内排序：主要是比较 + 移动 2个操作
  • 高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数

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

算法的复杂性：指算法本身的复杂度，非时间复杂度。

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

排序用到的结构与函数：顺序表

1
2
3
4
5
6
#define MAXSIZE 10
typedef struct
{
int r[MAXSIZE];
int length;
}SqList;

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

1
2
3
4
5
// 交换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;}

冒泡排序

冒泡：交换排序；两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

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(n2)。

简单选择排序

简单选择排序算法(Simple Selection Sort)就是通过n−i次关键字间的比较，从n−i+1个记录中选出关键字中最小的记录，并和第i(1≤i≤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);
	}
}

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

直接插入排序

直接插入排序(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−1n−1次，然后不需要进行移动，时间复杂度是O(n)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}$次。

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

希尔排序

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

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

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

这里的基本有序是指小的关键字基本在前面，大的基本在后面，不大不小的在中间。像{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，实际上增量的选取是非常关键的，现在还没有人找到一种最好的增量序列，但是大量研究表明，当增量序列是δ[k]=2t−k+1−1(0≤k≤t≤⌊log2(n+1)⌋)δ[k]=2t−k+1−1(0≤k≤t≤⌊log2(n+1)⌋)时，可以获得不错的效率，其时间复杂度是O(n32)O(n32)，要好于直接插入排序的O(n2)O(n2)。当然，这里需要注意的是增量序列的最后一个增量值必须等于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++;
			}
		}
	}
}

堆排序

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

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

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

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

堆

根结点一定是堆中所有结点最大或者最小者。

堆--数组

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

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()中第一个循环所做的事情，第二个循环也就是第二步，进行堆排序，逐步将每个最大值的根结点和末尾元素进行交换，然后再调整成最大堆，重复执行。

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

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

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

在正式排序的时候，第ii取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离是⌊log2i⌋+1)，并且需要取n−1n−1次堆顶记录，因此，重建堆的时间复杂度是O(nlogn)。

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

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

归并排序

归并排序(Merging Sort)就是利用归并的思想实现的排序方法，它的原理是假设初始序列有nn个记录，则可以看成是nn个有序的子序列，每个子序列的长度为1，然后两两合并，得到⌈n2⌉⌈n2⌉(⌈x⌉⌈x⌉表示不小于xx的最小整数)个长度为2或1的有序子序列；再两两合并，⋯⋯⋯⋯，如此重复，直至得到一个长度为nn的有序序列为止，这种排序方法称为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)，并且无论是最好、最坏还是平均都是同样的时间性能。另外，在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果，并且递归时需要深度为log2n的栈空间，因此空间复杂度是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];
	}
}

非递归版本的归并排序算法避免了递归时深度为log2n的栈空间，空间复杂度是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()每次都划分得很均匀，如果排序nn个关键字，其递归树的深度技术⌊logn⌋+1⌊logn⌋+1，即需要递归log2nlog2n次，其时间复杂度是O(nlogn)O(nlogn)。而最坏的情况下，待排序的序列是正序或逆序，得到的递归树是斜树，最终其时间复杂度是O(n2)O(n2)。

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

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

排序

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

排序算法指标对比

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

简单算法：冒泡、简单选择、直接插入。
改进算法：快速、堆、希尔、归并。
从平均情况看，快速、堆、归并三种改进算法都优于希尔排序，并远远胜过3种简单算法。

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

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

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

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

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

Thanks!