Ch8 排序

排序算法的复杂度

类型	排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	链式存储结构
交换	冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	适用
交换	快速排序	$O(nlogn)$	$O(n^2)$	$O(nlogn)$	$O(logn)$	不稳定	不适用
插入	直接插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	适用
插入	希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n^{1.3})$	$O(1)$	不稳定	不适用
选择	直接选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	适用
选择	堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定	不适用
归并	归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定	适用
	基数排序	$O(NM)$	$O(NM)$	$O(NM)$	$O(M)$	稳定	适用

• 归并排序可以通过手摇算法将空间复杂度降到 O (1)，但是时间复杂度会提高。

• 基数排序时间复杂度为 O (N*M)，其中 N 为数据个数，M 为数据位数。

口诀： 插冒归，稳 选冒插，方 快归堆 n 老 基你太稳

插入排序 (Insertion Sort)

每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列。

希尔排序 (Shell Sort)

把相隔某个增量的记录组成一个子表，对每个子表分别进行直接插入排序。

冒泡排序 (Bubble Sort)

从后往前（或从前往后）两两对比。

快速排序 (Quick Sort)

基于分治法，每次选区域的第一个为枢轴，每一轮排序完成后枢轴左边都小于（大于）枢轴，右边都大于（小于）枢轴，然后再对枢轴两边的区域分别进行递归快速排序，直到完全有序。查看解析

 
//划分区域方法
int Partition(ElemType A[],int low,int high){
	ElemType pivot=A[low];//第一个元素设为枢轴
	while(low < high){
		while(low < high && A[high] >= pivot) --high;
		A[low]=A[high];//将比枢轴小的元素移动到左边low指针
		while(low < high && A[low]<=pivot) ++low;
		A[high]=A[low];//将比枢轴大的元素移动到右边high指针
	}
	A[low]=pivot;//最后把枢轴的元素放到最终的位置
	return low;//返回枢轴的最终位置
}
 
void QuickSort(ElemType A[],int low,int high){
	if(low<high){//递归的跳出条件
		int pivotpos=Partition(A,low,high);//获取枢轴位置；
		QuickSort(A,low,pivotpos-1);//枢轴左边排序
		QuickSort(A,pivotpos+1,high);//枢轴右边排序
	}
}
 
 

选择排序 (Selection Sort)

每一趟循环时确定一个最小（最大）的元素，移动到有序的位置。

归并排序 (Merge Sort)

堆排序 (Heap Sort)

1. 构建一个大根堆（小根堆）
2. 将根节点（最大值）与堆尾互换，堆的大小减小 1，然后使用自顶向下 调整堆
3. 重复步骤 1、2 直到堆的大小为 1

基数排序 (Radix Sort)

1. 初始化位数 $k=1$
2. 对学号的第 $k$ 位执行“计数排序”。完成后，数据会根据第 $k$ 位从小到大排序
3. 将 $k$ 增加 1 ，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束

内部排序算法的选择

1. 若 $n$ 较小，可采用插入排序 (Insertion Sort) 或选择排序 (Selection Sort)，当记录本身信息量较大时，用移动次数较少的选择排序较好。
2. 若 $n$ 较大，应采用时间复杂度为 $O(nlo{g}_{2}n)$ 的排序算法：快速排序 (Quick Sort) 、堆排序(Heap Sort) 或归并排序 (Merge Sort)。
3. 若文件的初始状态已经按关键字基本有序，则选用插入排序 (Insertion Sort) 或者冒泡排序 (Bubble Sort) 较好。
4. 若 $n$ 很大，记录的关键字位数较少且可以分解时，采用基数排序 (Radix Sort) 较好。
5. 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

外部排序

外部归并算法

外排序分为两个步骤

1. 预处理
   • 首先，根据可用内存的大小，将外存上含有 $n$ 个纪录的文件分成若干长度为 $t$ 的子文件（或段）
   • 其次，利用内部排序的方法，对每个子文件的 $t$ 个纪录进行内部排序
   • 这些经过排序的子文件（段）通常称为顺串 (run)，顺串生成后即将其写入外存。这样在外存上就得到了 $m$ 个顺串 ( $m=[n/t]$ )
2. 合并排序：对这些顺串进行归并，使顺串的长度逐渐增大，直到所有的待排序的记录成为一个顺串为止。

$外部排序总时间=内部排序时间+外存信息读/写时{间}^{主要\ast }+内部归并时间$

外部排序过程中的时间代价主要考虑访问磁盘的次数，即 I/O 次数。外部信息读写的时间远远大于内部排序和内部归并的时间，因此应着力减少 I/O 次数。

多路平衡归并和败者树

采用败者树的方法来实现 k 路归并，增加归并路数，可减少归并趟数，进而减少总的磁盘 I/O 次数。

在做 $m$ 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置 $2m$ 个输入缓冲区和 2 个输出缓冲区。

原因：

1. 增加一个输出缓冲区，当一个输出缓冲区满时，通知通道进行输出，同时归并程序向第二个输出缓冲区填充数据，这就实现了内部归并和输出的并行
2. 增加$m$个输入缓冲区，当$m$个缓冲区正在运行时，外部可以向正在工作的$m$个缓冲区对应的第二个缓冲区（也就是增加的$m$个缓冲区）写入数据，这就实现了输入和内部归并的并行

定义

1. 败者树是一颗完全二叉树
2. 败者树的叶子结点保存的是我们的输入缓冲区（每个选手的值）
3. 败者树的非叶子结点保存我们的当前的比较中败者的对应的输入缓冲区的指针（比较的两个数，大者为失败、小的为胜利者）
4. 败者树根保存亚军，根上面还有一个节点 保存冠军

置换 - 选择排序

用于生成外部排序的初始归并段

1. 在所有待排序文件中，输入 $w$ 个记录到工作区 WA
2. 从 WA 中取出关键字最小的记录，更新 MINIMAX
3. 将 MINIMAX 输出到 FO 中
4. 若 FI 不空，则输入一个记录到 WA 中
5. 从 WA 所有比 MINIMAX 大的记录中的最小的记录，更新为新的 MINIMAX
6. 重复 3. ~ 5. ，直到在 WA 中选不出新的 MINIMAX ，则该归并段结束，开始新的归并段
7. 重复 2. ~ 6. 直至 WA 为空，由此获得全部初始归并段

排序过程

输出文件 FO	工作区 WA	输入文件 FI
-	-	17,21,05,44,10,12,56,32,29
-	17,21,05	44,10,12,56,32,29
05	17,21,44	10,12,56,32,29
05,17	10,21,44	12,56,32,29
05,17,21	10,12,44	56,32,29
05,17,21,44	10,12,56	32,29
05,17,21,44,56	10,12,32	29
05,17,21,44,56 #	10,12,32	29
10	29,12,32	-
10,12	29,32	-
10,12,29	32	-
10,12,29,32	-	-

最佳归并树

$k$ 路平衡归并使用 $k$ 叉 哈夫曼树，树的带权路径长度 WPL 就是归并过程中的总读记录数，所以 $I/O次数=2\times WPL$

补虚段问题

在一般情况下，对于 k 路平衡归并来说，若 $(m-1)\mathrm{mod}(k-1)=0$ ，则不需要增加虚段；否则需附加 $k-(m-1)\mathrm{mod}(k-1)-1$ 个虚段。