[数据结构与算法]王道408数据结构——第八章 排序

一、排序定义

重新排列表中的元素，使表中的元素满足按关键字有序。
算法的稳定性：带排序表中关键字相同的元素，其相对次序在排序前后不变，这称这个排序算法是稳定的。算法是否稳定并不能衡量一个算法的优劣。如果带排序表中的关键字均不重复，则排序结果是唯一的，算法的稳定性就无关紧要。

大部分的内部排序都需要执行比较和移动操作。通过比较两个关键字的大小，确定对应元素的前后关系；然后通过移动元素以达到有序。

在基于比较的排序方法中，每次比较两个关键字大小之后，仅出现两种可能的转移。因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 n 个关键字随机分布时，任何借助比较的排序算法，至少需要$O(n{\log }_{2}n)$的时间。

二、插入排序——直接插入排序

1. 描述

插入排序是一种简单直观的排序方法，其基本思想是将一个待排序的记录按其关键字大小插入前面已排好序的子序列。

插入排序通常采用就地排序，在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素腾出插入空间。

2. 代码和示例

下面是直接插入排序的代码

void insertSort(ElemType A[], int n){
	int i, j;
	for(i = 2; i <= n; i++){  // 依次对A[2]到A[n]进行插入排序
		if (A[i] < A[i-1]){  // 如果当前元素小于其前驱，将其插入前面序列
			A[0] = A[1];  // 哨兵，A[0]不存放元素
			for(j = i-1; A[0] < A[j]; j--)  // 从后往前查找待插入位置
				A[j+1]  = A[j];  // 元素挨个往后挪位
			A[j+1] = A[0];  // 最后一次循环，j指向待插入点的前一个位置。
		}
	}
}

3. 空间效率

就地排序，仅使用了常数个辅助单元，空间复杂度为$O(1)$

4. 时间效率

排序过程中，向有序子表中逐个插入元素的操作进行了n-1趟；每趟操作都分为比较关键字和移动元素，次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需一次比较而不需要移动元素。时间复杂度为$O(n)$；
在最坏情况下。表中元素的顺序刚好与排序结果相反（逆序），总的比较次数达到最大，为${\sum }_{i=2}^{n}i$，总的移动次数也达到最大，为${\sum }_{i=2}^n(i+1)$；
在平均情况下，考虑待排序表中的元素是随机的，此时取最好与最坏情况的平均值作为平均情况的时间复杂度。总的比较次数和总的移动次数均为$\frac{n^2}{4}$。
因此，直接插入排序的时间复杂度为$O(n^2)$。

5. 稳定性

每次插入元素总是从后往前先比较在移动，算法是稳定的。

6. 适用性

直接插入排序算法时使用与顺序储存（大部分排序算法仅适用于顺序储存的线性表）和链式储存。

其更适用于基本有序、数据量不大的排序表。

三、插入排序——折半插入排序

1. 描述

对于顺序表，对插入位置的查找过程可以采用折半查找来实现。确定待插入位置后，再统一向后移动元素。

2. 时间效率

折半插入排序减少了比较元素的次数，总比较次数约为$O(n{\log }_{2}n)$，该比较次数与表的初始状态无关，仅取决于表中元素的个数；
而元素的移动次数并未改变，仍依赖于表的初始状态。
因此，时间复杂度仍为$O(n^2)$。

但对于数据量不是很大的排序表，折半插入排序往往表现出很好的性能。

3. 稳定性

折半插入排序是一种稳定的排序方法。

四、插入排序——希尔排序（缩小增量排序）

1. 描述

基本思想：先将待排序表分割成若干形如$[i,i+d,i+2d,?,i+kd]$的特殊子表，即把相隔某个增量的记录组成一个子表，对各个子表进行直接插入排序；当整个表中的元素已呈“基本有序”时,再对全体记录进行一次直接插入排序。

希尔排序的过程如下：

1. 先取一个小于 n 的步长 $d_1$；
2. 把表中的全部记录分成$d_1$组：所有距离为$d_1$倍数的记录放在同一组；
3. 在各组内进行直接插入排序；
4. 取第二个步长$d_2(d_2<d_1)$，重复第二、三步。
5. 不断取更大步长，直到$d_t=1$，即所有记录已放在同一组中，再进行一次直接插入排序。由于此时已经具有了较好的局部有序性，故可以很快得到最终结果。

通常步长$d_i$的取值为$d_1=\frac{n}{2},d_{i+1}=?\frac{d_i}{2}?,d_{最后一个}=1$

2. 代码和示例

希尔排序的代码如下

void shellSort(Elemtpye A[], int n){
	int dk, i, j;
	for(dk = n/2; dk >= 1; dk = dk/2){
		// 将各个子表的直接插入排序分解，合并为一个循环，一次循环过程仅按顺序处理一个元素
		// 从第1个子表的第二个元素开始，第二次循环进行第2个子表的第二个元素
		for(i = dk+1; i < n; ++i){
			if(A[i] >= A[i-dk])  // 仅在当前元素无序时进行排序
				continue;
			A[0] = A[i];  // A[0]不是哨兵，仅暂存元素
			// j小于等于0时，说明该元素在该子表的已排序序列中最小
			for(j = i-dk; j >= 0 && A[0] < A[j]; j -= dk)  
				A[j+dk] = A[j];
			A[j+dk] = A[0];
		}
	}
}

3. 空间效率

仅使用了常数个辅助单元，空间复杂度为$O(1)$

4. 时间效率

当n在某个特定范围时，希尔排序的时间复杂度约为$O(n^{1.3})$。
在最坏情况下，希尔排序的时间复杂度为$O(n^2)$。

5. 稳定性

当相同关键字的记录被划分到不同子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

6. 适用性

希尔排序对较大规模的排序都可以达到很高的效率。

仅适用于顺序存储的线性表。

五、交换排序——冒泡排序

1. 描述

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

基本思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完，这称为一趟冒泡。一趟冒泡的结果是将最小（或最大）元素交换到待排序的第一个位置。下一趟冒泡时，已确定位置的元素不再参与比较。这样最多做n-1趟冒泡就可以把所有元素排好。

冒泡排序中所产生的有序子序列一定是全局有序的，每趟排序都会将一个元素放在其最终位置。

2. 代码和示例

冒泡排序算法代码如下

void bubbleSort(ElemType A[], int n){
	for(i = 0; i < n-1; i ++){
		flag = false;  // 标志位，记录本趟冒泡是否发生交换
		for(int j = n-1; j > i; j--){  // 一趟冒泡，顺序与外层循环相反
			if(A[j-1] > A[j]){ 
				swap(A[j-1], A[j]);
				flag = true;
			}
		}
		if( !flag )  // 若某趟冒泡过程没有发生交换，说明表已经有序
			return;
	}
}

3. 空间效率

仅使用了常数个辅助单元，空间复杂度为$O(1)$。

4. 时间效率

最好情况下，当初始序列有序时，第一趟冒泡标志位flag仍为false，直接跳出循环，比较次数为n-1，移动次数为0，时间复杂度为$O(n)$；
最坏情况下，当初始序列逆序时，需要进行n-1趟排序，第 i 趟排序要进行 n-i 次关键字的比较，而且每次比较后都必须进行三次移动来交换元素的位置。$$比较次数=\sum _{i=1}^{n?1}(n?i)=\frac{n(n?1)}{2}，移动次数=\sum _{i=1}^{n?1}3(n?i)=\frac{3n(n?1)}{2}$$从而最坏情况下时间复杂度为$O(n^2)$；
平均情况下，时间复杂度为$O(n^2)$。

5. 稳定性

冒泡排序时一种稳定的排序方法。
如果把代码中判断是否逆序的条件由“＞”改为“≥”，则算法变得不稳定。

六、交换排序——快速排序

1. 描述

快速排序的基本思想是基于分治法的：在待排序表中选取一个元素，称为枢轴（或称基准，常取首元素）。通过一趟排序，将待排序表分成两部分，一部分中所有元素均小于枢轴，另一部分元素均大于枢轴，两部分分别位于枢轴元素的两侧，这个过程称为一趟快速排序（或一次划分）。然后递归地分别对两个子表重复上述过程，直到每部分只有一个元素或空为止，此时所有元素都放在了最终位置。

快速排序并不产生有序子序列，但每趟排序后会将枢轴元素放在最终位置上。

2. 代码和示例

一趟快速排序是一个交替搜索和交换的过程，算法如下

void quickSort(ElemType A[], int low, int high){
	if(low >= high)  // 递归跳出条件。只有一个元素或为空
		return;
	// 一趟快排，将表划分为两个子表，返回枢轴位置
	int pivotpos = partition(A, low, high); 
	quickSort(A, low, pivotpos-1);  // 对左子表进行递归
	quickSort(A, pivotpos+1, high);  // 对右子表进行递归
}

// 一趟划分，交替进行搜索交换
int partition(ElemType A[], int low, int high){
	ElemType pivot = A[low];  // 设为枢轴
	while(low < high){  
		// 从high往前搜索，找到最近的小于枢轴的元素，
		// 将其置入枢轴或者上一次交换留出空位中
		while(low < high && A[high] > pivot) 
			low--;
		A[low] = A[high];
		// 从low往后搜索，找到最近的大于枢轴的元素，
		// 将其置入上一次交换留出的空位中。
		while(low < high && A[low] < pivot)
			high++;
		A[high] = A[low];
	}
	A[low] = pivot;  // 将枢轴元素置入交替搜索后留出的空位中。
	return pivot;  // 返回枢轴位置
}

3. 空间效率

快排是递归地，需要借助一个递归工作栈来保持每层递归调用的必要信息，容量与递归调用的最大深度一致。
最好情况下，空间复杂度为$O({\log }_{2}n)$；
最好情况下，因为要进行n-1次递归调用，栈的深度为$O(n)$
平均情况下，栈的深度为$O({\log }_{2}n)$。

4. 时间效率

快速排序的运行时间和划分是否对称有关。
最好情况下，partition()可以做到最平衡的划分，得到的两个子问题大小都不大于n/2，这种情况下快速排序的运行速度将大大提升，此时时间复杂度为$O(n{\log }_{2}n)$；
最坏情况下，划分的两个区域分别包含n-1个元素和0个元素。若初始表基本有序或基本逆序时，每层递归都出现最坏情况。此时时间复杂度为$O(n^2)$；
平均情况下的快速排序与其最佳情况的运行时间很接近，时间复杂度为$O(n{\log }_{2}n)$。

有很多方法可以提升算法的效率：一种方法时尽可能选择一个可以将数据平分的枢轴，如从序列的头尾和中间选取三个元素，选择三个元素的中间值作为枢轴；或随机从表中选取一个枢轴，这样做可以时最坏情况几乎不会出现。

快速排序是所有内部排序中平均性能最优的排序算法。

5. 稳定性

某一趟中，两个关键字相同的元素，从一个区间被交换到另一个区间的过程中，相对位置会发生变化。快速排序是一种不稳定的排序方法。

七、选择排序——简单选择排序

1. 描述

基本思想：每一趟排序后，将剩余待排序元素中选择关键字最小（或最大）的元素，放在其最终位置，最终位置的原有元素与其交换位置。

2. 代码

简单选择排序代码如下

void selectSort(ElemType A[], int n){
	for(int i = 0; i < n-1; i++){  // 到第n-1趟，待排元素只剩一个，就不用再选了
		int min = i;
		for(int j = i+1; j < n; j++){  // 选择待排序列中的最小元素
			if(A[j] > A[i])
				min = j;
		}
		if(min != i)
			swap(A[i], A[min]);
	}
}

3. 空间效率

仅使用常数个辅助单元，空间效率为$O(1)$。

4. 时间效率

在简单选择排序中，元素移动的次数很少，不会超过$3(n?1)$次，最好情况是移动0次（此时对应表已有序）。但元素的比较次数和序列的初始状态无关，始终是$\frac{n(n?1)}{2}$次，因此时间复杂度始终是$O(n^2)$

5. 稳定性

在第 i 趟把最小元素和第 i 个元素进行交换时，可能导致第 i 个元素与其后含有相同关键字元素的相对位置发生变化。简单选择排序是不稳定的。

八、选择排序——堆排序

1. 堆的定义

若n个关键字序列满足以下任一条件：
$$\{\begin{array}{lc}L(i)?L(2i)\wedge L(i)?L(2i+1)& (1?i??\frac{n}{2}?)\\ L(i)?L(2i)\wedge L(i)?L(2i+1)& \end{array}$$
该序列称为堆。

堆可以视为一棵完全二叉树，满足第一个条件的称为大根堆，其最大元素放在根节点，且堆的非叶结点的值均大于其左右子树。，满足第二个条件的称为小根堆。

2. 建堆（构造初始堆）

n个结点的完全二叉树，其最后一个非叶结点序号是$?\frac{n}{2}?$。从最后一个非叶结点开始往前一次遍历结点，对每一个以当前结点为根的子树进行检查：对于大根堆，若根结点关键字小于左右孩子，将左右孩子中较大者与之交换，小根堆反之；交换后可能破坏下一级的堆，因此对下一级的堆重复进行检查和交换，直到以当前结点为根的子树构成堆为止。

下面是建立大根堆的算法

void buildMaxHeap(ElemType A[], int len){
	for(int i = len/2; i > 0; i--)  // 从最小非叶结点开始，反复调整堆
		headAdjust(A, i, len);
}

void headAdjust(ElemType A[], int k, int len){
	A[0] = A[k];  // 暂存子树根节点
	for(int i = 2*k; i <= len; i *= 2){  // 沿key值较大的结点往下
		if(i < len && A[i+1] > A[i])  // 左右子树在顺序表中总是相邻
			i++;  // 选择key值较大的结点
		if(A[0] >= A[i])  // 当前堆已满足性质
			break;
		A[k] = A[i];  // 调整结点
		k = i;  // 进入较大叶结点的子树
	}
	A[k] = A[0];
}

调整的时间与数高h有关，为$O(h)$。
在建含 n 个元素的堆时，关键字的比较总次数不超过4n，时间复杂度为$O(n)$，这说明可以在线性时间将一个无序数组建成一个堆。

3. 删除结点

堆的删除通常在根节点处，此时需要重新调整结构以保持性质。

输出堆顶元素后，将堆底元素移到堆顶。再从堆顶元素开始向下调整，使其保持大堆顶的性质。

4. 插入结点

对堆进行插入时，先将新结点放在堆的末端，再对这新结点向上执行调整操作。

5. 算法与示例

下面给出堆排序算法，即依次删除根节点的算法

void heapSort(ElemType A[], int len){
	buildMaxHeap(A, len);  // 建立初始堆
	// 进行n-1趟交换和建堆过程。当i=1时，仅剩根节点，此时数组已经有序
	for(int i = len; i > 1;  
		// 输出堆顶元素（和堆底元素进行交换），此时数组中i~len的元素已经是全局有序的了
		swap(A[i], A[1]);  
		headAdjust(A, 1, i-1);  // 把剩余i-1个元素元素整理成堆
	}
}

建立初始堆的示例如下

输出根节点87，将最后一个叶节点09置于根的位置，将剩余元素调整成新堆调整

在堆的末端插入新结点，重新调整堆

6. 空间效率

仅使用了常数个辅助单元，空间复杂度为$O(1)$

7. 时间效率

建堆时间为$O(n)$，之后有n-1次向下调整操作，每次调整时间复杂度为O(h)。故在最好、最坏和平均情况下，堆排序的时间复杂度$O(n{\log }_{2}n)$。

8. 稳定性

在进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序时一种不稳定的排序方法。

9. 适用性

堆排序适合关键字较多的情况。

九、归并排序

1. 描述

假定待排序表含有n 个记录，则可将其视为n个有序的子表，每个子表长度为1。然后两两归并（称为2路归并排序），再将得到的长度为2或1的有序表两两归并，如此重复，直到合并成一个长度为n的有序表为止。

2. 代码和示例

递归形式的归并排序算法时基于分治的，分为分解和合并两个步骤

void mergeSort(ElemType A[], int low, int high){
	if(low < heigh){  // 递归推出条件，当low==heigh时，子表长度为1，停止分解
		int mid = (low + high) / 2;  // 分解：划分两个子表，对两个子表递归地进行排序
		mergeSort(A, low, mid); 
		mergeSort(A, mid+2, high);
		merge(A, low, mid, high);  // 归并：合并两个已经排序的子表得到新的排序结构
	}
}

// 设立一个辅助数组
ElemType *B = (ElemType *)malloc( (n+1)*sizeof(ElemType) );  

// 归并两个子表的过程与合并两个有序链表的算法过程类似
void merge(ElemType A[], int low, int mid, int high){
	for(int i = low; i <= high; i++)  // 将两个子表中所有元素复制到B中的对应位置
		B[i] = A[i];
	for(int i = low; int j = mid+1; int k = low; i <= mid && j <= high; k++){
		if(B[i] <= B[j])
			A[k] = B[i++];
		else
			A[k] = B[j++];
	}
	while(i <= mid)
		A[k++] = B[i++];
	while(j <= high)
		A[k++] = B[j++];
	
}

3. 空间效率

merge()操作中，辅助空间刚好为n个单元，空间复杂度为$O(n)$。

4. 时间效率

每趟归并的时间复杂度为$O(n)$，需要进行$?{\log }_{2}n?$趟归并，所以算法的时间复杂度为$O(n{\log }_{2}n)$。

一般而言，对于N个元素进行 k 路归并排序时，排序的趟数 m 满足$k^m=N$，从而$m=?{\log }_{k}N?$。

从单个记录起进行两两归并并不值得提倡，通常将它和直接插入排序结合。改进后的归并排序仍是稳定的。

5. 稳定性

merge()操作并不会改变相同关键字记录的相对次序，算法是稳定的。

十、基数排序

1. 描述

基数排序十一种很特别的排序方法，它基于比较和移动进行排序，而基于关键字各位的大小进行排序。技术排序是一种借助多关键字排序的思想以对单逻辑关键字进行排序的方法。

假设长度为 n 的线性表中每个结点$a_j$的关键字由 d 元组$$(k_j^{d?1},k_j^{d?2},?,k_j^1,k_j^0)$$组成，满足$0\le k_j^i\le r?1$。其中$k_j^{d?1}$称为最主位关键字，$k_j^0$称为最次位关键字。

为实现多关键字排序，通常由两种方法：

• 最高位优先（MSD）：按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
• 最低位优先（LSD）：按关键字位权重递增依次进行排序，最后形成一个有序子序列。

2. 算法和示例

下面描述以 r 为基数的最低位优先基数排序的过程
在排序过程中，使用 r 个队列$Q_0,Q_1,?,Q_{r?1}$。基数排序的过程如下：
从i=0开始（数字最低位），依次做一次“分配”和“收集”。

• 分配：开始时，把$Q_0,Q_1,?,Q_{r?1}$各个队列置空，然后依次考察线性表中的每个结点$a_j(j=0,1,?,n?1)$，若$a_j$关键字$k_j^i=k$，就把$a_j$放进$Q_k$队列中。
• 收集：把$Q_0,Q_1,?,Q_{r?1}$各个队列首位相接，得到新的结点序列，从而组成新的线性表。

通常采用链式基数排序，假设对如下10个记录进行排序：

每个关键字是1000以下的正整数，由3位子关键字$K^1{K}^2{K}^3$构成，分别代表百位、十位、个位，一共需要进行三趟分配-收集操作。基数r=10，在排序过程中需要借助10个链队列。

第一趟分配用最低位关键字（个位）$K^3$进行。将所有$K^3$相等的记录分配到同一个队列，然后进行收集。

第二趟分配用次低位关键字（十位）$K^2$进行，将所有$K^2$相等的记录分配到同一个队列，然后进行收集。

第三趟分配用最高位关键字（百位）$K^1$进行，将所有$K^3$相等的记录分配到同一个队列，然后进行收集。自此整个排序结束

3. 空间效率

一趟排序需要辅助空间为 r（r个队列，r个队头指针和队尾指针）。空间复杂度为$O(r)$。

4. 时间效率

基数排序需要进行 d 趟分配和收集，一趟分配需要$O(n)$，一趟收集需要$O(r)$。所以基数排序的时间复杂度为$O(d(n+r))$，其与序列的初始状态无关。

5. 稳定性

基数排序是稳定的。

十一、排序算法的比较

算法种类	时间复杂度			空间复杂度	是否稳定
	最好情况	最坏情况	平均情况
直接插入排序 （插入排序）	O(n)	O(n2)	O(n2)	O(1)	稳定
冒泡排序 （交换排序）	O(n)	O(n2)	O(n2)	O(1)	稳定
简单选择排序 （选择排序）	O(n2)	O(n2)	O(n2)	O(1)	不稳定
希尔排序 （插入排序）	依赖增量函数			O(1)	不稳定
快速排序 （交换排序）		O(n2)		最坏情况下是O(n2)	不稳定
堆排序 （选择排序）				O(1)	不稳定
2路归并排序				O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定

• 在实际应用中，快速排序往往可以优于其他算法，被认为是目前基于比较的内部排序中最好的方法。
• 冒泡排序和堆排序每趟处理后都能产生当前的最大值或最小值。
• 快速排序一趟处理就能确定一个元素的最终位置。
• 若 n 较小，可以采用直接插入排序或简单选择排序；
  • 由于直接插入排序所需的记录移动次数较简单选择排序多，当记录本身信息量较大时，选用简单选择排序较好。
• 若文件的初始状态已经按关键字基本有序，选用直接插入排序或冒泡排序。
• 若 n 较大，则应采用时间复杂度为$O\log 2n)$的排序方法：快速排序、推排序或归并排序；
  • 当关键字随机分布时，快速排序平均时间最短；
  • 堆排序所需的辅助空间少于快速排序，且不会出现快速排序可能出现的最坏情况；
  • 若要求排序稳定，则可选用归并排序。
• 若 n 很大、记录的关键字位数较少且可以分解时，采用基数排序较好
• 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以采用链表作为存储结构。