《数据结构》学习系列——排序（下）

选择排序

思想
对待排序的文件进行n次选择，其中第i次选择第i小（大）的记录放在第i（n-i+1）个位置上

算法

直接选择排序
堆排序

直接选择排序

直接选择排序思想：
- 选择第i大的记录——在剩余的n−i+1个记录中进行一趟比较，确定出第i大记录，放在第n−i+1个位置上。
例如，第i趟比较（i=1,…,n−1）在前面n−i+1个待排序记录中选出关键词最大的记录，作为有序记录序列的第n−i+1个记录。待到第n−1趟作完，待排序记录只剩下1个时，算法结束

伪代码

算法SSort（R，n)
// 直接选择排序算法，该算法排序文件(R1,R2,...,Rn)
// SS1[排序]
FOR j=n TO 2 STEP -1 DO
{
	t←1
	FOR i=2 TO j DO   // t始终指向较大的那个
	{
		IF Kt<Ki  THEN 
		{
			t←i  	//找子序列里最大的放在子序列的末尾
			Rj>Rt   //将Rt放到第j个位置上
		}
	}
}

算法分析

直接选择排序的关键词比较次数与记录的初始排列无关。假定整个待排序文件有 n n n个记录，第 i i i趟选择具有最大关键词的记录所需的比较总次数是 n − i n-i n−i次。因此，总的关键词比较次数为

( n − 1 ) + ( n − 2 ) + … + 1 = n ( n − 1 ) 2 (n-1)+(n-2)+\ldots+1 = \frac{n(n-1)}{2} (n−1)+(n−2)+…+1=2n(n−1)

记录交换次数是选择的趟数： n − 1 n-1 n−1。
直接选择排序算法
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)（包括最好、最坏和平均）
- 稳定性：不稳定的排序方法
- 空间复杂度： O ( 1 ) O(1) O(1)
- 优点：简单、书写容易

锦标赛排序（树选择排序）

对简单选择排序方法的改进，简单选择排序时间大部分都浪费在关键词的比较上，而锦标赛排序刚好用树保存了前面比较的结果，下一次选择时直接利用前面比较的结果大大减少了比较次数

淘汰赛思想

对于 n n n个记录的关键词，进行两两比较，得到 ⌈ n 2 ⌉ \left\lceil \frac{n}{2} \right\rceil ⌈2n⌉个比较的优胜者（关键词大者），作为第一步比较的结果保留下来。然后对这 ⌈ n 2 ⌉ \left\lceil \frac{n}{2} \right\rceil ⌈2n⌉个记录再进行关键词的两两比较， … … \ldots\ldots …… 如此重复，直到选出一个关键词最大的记录为止。在图例中，最下面是记录排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的记录的关键词

《数据结构》学习系列——排序（下）-LMLPHP

如果 n n n不是 2 2 2的 k k k次幂，则让叶结点数补足到满足 2 k − 1 < n ≤ 2 k 2^{k-1} < n \leq 2^k 2k−1<n≤2k的 2 k 2^k 2k个。叶结点上面一层的非叶结点是叶结点关键词两两比较的结果。最顶层是树的根

比赛树概念

每次两两比较的结果是把关键词大者作为优胜者上升到双亲结点，称这种树为比赛树
位于最底层的叶节点叫做比赛树的外结点，非叶节点称为比赛树的内结点。每个结点除了存放记录的关键词外，还存放了此对象在满二叉树中的序号
比赛树最顶层是树的根，表示最后选择出来的具有最大关键词的记录

算法分析

除第一次选择具有最大关键词的记录需要进行n-1次关,键词比较外，重构比赛树选择具有次大、再次大关键词记,录所需的关键词比较次数均为 O ( l o g 2 n ) O(log_2n) O(log2n)。总关键词比较,次数为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
直接选择排序之所以不够高效就是因为没有把前面比较的,结果保留下来，每次都有很多重复的比较，而锦标赛排序,利用了之前的比较结果
但对于n个待排元素，锦标赛算法需要至少2n-1个结点来,存放比赛树，故这是一个拿空间换时间的算法

堆排序

完全二叉树中任意结点的关键词大于等于它的两个孩子结构的关键词。把这样的数据结构称为堆（大根堆）
大根堆，小根堆
- 大根堆中根结点的关键词最大
- 小根堆中根结点的关键词最小
  
  思想
如果数组R中存放了堆，那么R[1]是最大的记录，将R[1]和R[n]的交换，使得最大记录放在R[n]的位置。然后构成一个堆。
调整后R[1]是R[1]，R[2]，…，R[n-1]中最大的。然后再交换R[1]与R[n-1]，使R[n-1]中放入次最大的记录。再对R[1]，R[2]，…，R[n-2]进行调整，使之成为新堆，再进行类似的交换和调整，反复进行，直到调整范围只剩下一个记录R[1]为止。
此时R[1]是n个记录中最小的，且数组R[1…n]中记录已经按从小到大排列了

堆排序算法的粗略描述如下：

建立包含 R 1 , R 2 , . . . , R n R_1, R_2, ..., R_n R1,R2,...,Rn 的堆； //建堆
FOR i=n TO 2 STEP -1 DO
- R 1 ↔ R i R_1 \leftrightarrow R_i R1↔Ri； //交换位置
- 重建包含 R 1 , R 2 , . . . , R i − 1 R_1, R_2, ..., R_{i-1} R1,R2,...,Ri−1 的

伪代码

算法 Restore(R, f, n) // 对任意有孩子结点的结点进行调整
    n: 此次需要排序的元素总数；f: 树中待调整的某个有孩子结点的结点
// R1 [初始化] 
j ← f
// R2 [建堆]
WHILE j ≤ ⌊n/2⌋ DO 	// 是否有孩子结点
{
	IF (2j < n) AND (K[2j] < K[2j+1])	THEN m ← 2j+1
	ELSE m ← 2j 			// m 指向孩子结点中较大的那个
    IF K[m] > K[j] THEN (R[m] ↔ R[j], j ← m) // m 指向的节点与结点比较
    ELSE j ← n // 已经是较大的那个，所以终止循环
}

HeapSort(R, n) // 堆排序算法
{
	// HS1 [初始建堆]
	FOR i = ⌊n / 2⌋ TO 1 STEP -1 DO Restore(R, i, n)
	// HS2 [排序]
	FOR i = n TO 2 STEP -1 DO
    {
    	R1 ↔ Ri
    	Restore(R, 1, i - 1)
    }

合并排序法

分治法的思想
将一个输入规模为 n的问题分解为 k个规模较小的子问题，这些子问题互相独立且与原问题相同，然后递归地求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解

算法思路

初始调用采用DCSort(1, n, X)。

分治排序包括三个步骤：

“分”，将记录划分为若干子部分，一般为二分，可以证明多分策略效果不会优于二分策略；
“治”，对部分递归执行算法；“组”，将子部分处理后的结果整合在一起。

由于“治”是递归调用过程，分治排序的重点在“分”和“组”两步，而实际上具体的算法往往侧重其中的某一步，
如：合并排序侧重在“组”，分的过程就是简单的二分；快速排序侧重在“分”，在“分”的过程中调整了两个子集的元素，而“组”过程无需任何操作。

伪代码

算法 DCSort(p, q, X)
// 数据集 X 有 n 个记录, DCSort(p, q, X) 对 X(p) 到 X(q) 之间的元素排序, 1 ≤ p ≤ q ≤ n

// DCSort1. [如果记录集足够小，则采用简单排序算法（如直接插入排序）处理]
IF SMALL(p, q) THEN RETURN(InsertSort(p, q, X))

// DCSort2. [划分记录集为两部分，分别排序，再将结果组合]
m ← DIVIDE(p, q)
RETURN(COMBINE(DCSort(p, m, X), DCSort(m + 1, q, X)))

二路合并排序

合并：把两个，或多个有序文件组成一个单一的有序文件
两个文件的合并

若当 i 和 j 都在两个表内变化时，根据 A [ i ] A[i] A[i] 与 B [ j ] B[j] B[j] 的关键词比较大小，依次把关键词小的对象排放到新表 X [ k ] X[k] X[k] 中
当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表 X 中

![在这里插入图《数据结构》学习系列——排序（下）-LMLPHP

两个有序文件合并成一个大的有序文件

算法 Merge(R, t, m, n, X)
// t 是序列开始的位置，m 是序列结束的位置，n 是第二个序列的长度，X 是合并的序列，k 是合并序列的下标

M1 [初始化给每个文件一个头指针]
    i ← t
    j ← m + 1
    k ← 1

M2 [比较 i 和 j 所指记录]
    WHILE (i ≤ m) AND (j ≤ n) DO
        IF R[i] ≤ R[j] THEN
            X[k] ← R[i]
            i ← i + 1
        ELSE
            X[k] ← R[j]
            j ← j + 1
        k ← k + 1

M3 [复制余留记录项]
    WHILE (i ≤ m)
        X[k] ← R[i]
        i ← i + 1
        k ← k + 1
    WHILE (j ≤ n)
        X[k] ← R[j]
        j ← j + 1
        k ← k + 1

《数据结构》学习系列——排序（下）-LMLPHP

算法 Merge(R, t, m, n, X)
- 假定文件 ( R t , R t + 1 , … , R m ) (R_t,R_{t+1},…,R_m) (Rt,Rt+1,…,Rm)和文件$(R_{m+1},…,R_n)都已经排序，该算法合并这两个文件后得到排序好的大文件 $(X_t,X_{t+1},…,X_n)
算法 MPass(R, n, length, X)
- 一趟合并算法，该算法执行一趟合并过程，将文件 R 中长度为 length 的所有子文件合并到文件 X 中，n 是 R 的记录个数，该函数调用 Merge() 函数；
算法 MSort(R, n)
- 该函数调用函数 MPass()，直接两路合并排序，X 是辅助文件；

算法 MSort(R, n) // 直接两路合并排序算法，X是辅助文件，其记录结构与R相同

MS1 [初始化]
    length ← 1

MS2 [交替合并]
    WHILE length < n DO
        {
        	MPass(R, n, length, X)
        	length ← 2 * length
        	MPass(X, n, length, R)
        	length ← 2 * length
        }

算法 MPass(R, n, length, X)
/* 一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数 */

// MP1 [初始化]
i ← 1

// MP2 [合并相邻的两个长度为length的子文件]
WHILE i ≤ n - 2*length + 1 DO
	{
		Merge(R, i, i+length-1, i+2*length-1, X)
        i ← i + 2*length
	}
// MP3 [处理余留的长度小于2*length的子文件]
	IF i + length - 1 < n THEN Merge(R, i, i+length-1, n, X)
    ELSE FOR j = i TO n DO X[j] ← R[j]

在归并排序算法中，函数 MPass() 做一趟两路归并排序，要调用 merge() 函数 ⌈ n / ( 2 × length ) ⌉ ≈ O ( n / length ) \lceil n/(2 \times \text{length}) \rceil \approx O(n/\text{length}) ⌈n/(2×length)⌉≈O(n/length) 次，函数 MSort() 调用 MPass() 正好 ⌈ log ⁡ 2 n ⌉ \lceil \log_2 n \rceil ⌈log2n⌉ 次，而每次 merge() 要执行比较 O ( length ) O(\text{length}) O(length) 次，所以算法总的时间复杂度为 O ( n log ⁡ 2 n ) O(n \log_2 n) O(nlog2n)
归并排序占用附加存储空间较大，需要另外一个与原待排序对象数组同样大小的辅助数组。这是归并算法的缺点。
归并排序是一个稳定的排序方法

合并排序算法的缺点：
- 当数据集非常小时，比如只有2个元素，仍然采用分治策略，影响效率。
- Merge算法基于元素移动，当元素比较大时，赋值操作会比较费时。
针对这两个问题的解决办法：
- 对于非常小的数据集，以及前几次归并动作，调用直接插入排序算法。
- 将数组存储改为链表存储，这样记录移动就变为指针移动了。

总结

《数据结构》学习系列——排序（下）-LMLPHP

K3njuan