7.排序

排序指整理文件中的记录, 使得按给定关键字递增或递减的次序排列:

• 如果存在多个相同关键字的记录, 排序之后这些记录之间的相对次序不变, 则称这种排序方法是 稳定 的; 反之则为 不稳定 的.
• 若整个待排序数组都在内存中处理, 不涉及数据的内外村交换, 称这种排序方法为 内部排序; 反之则为 外排序.

本书仅讨论内部排序, 且假定关键字为整数, 按递增顺序排序.

评价排序算法的标准包括:

• 时间开销: 一般通过排序过程中关键字的比较次数和记录移动次数衡量
• 空间开销: 若空间开销相对于数据量来说是一个常数, 则称排序方法为就地排序
• 算法本身的复杂度

插入排序

基本思想: 每次将一个记录插入到前面已排好序的文件中的适当位置.

直接插入排序

1. 待排序记录被划分为有序区和无序区. 有序区最开始只包含第一个记录, 其余为无序区
2. 每次从无序区取第一个元素, 插入到有序区适当位置
3. n-1 插入后, 无序区为空, 排序完毕

希尔排序 (缩小增量排序)

1. 分组: 取定一个小于记录数的整数 d 作为第一个增量, 把全部记录分成 d 个组, 所有下标距离为 d 的倍数的记录为一组
2. 排序: 在各组内进行直接插入排序. 然后再取一个小于 d 的整数作为第二个增量
3. 重复上述步骤, 直到增量为 1

交换排序

基本思想: 两两比较记录, 发现次序相反则交换.

冒泡排序: 使较小者从底部逐渐移向顶部

1. 从最后位置到第一个位置, 依次进行相邻位置的两两比较, 若次序相反就交换. 第一趟排序结束, 此时第一个元素为最小
2. 从最后位置到第二个位置, 依次进行相邻位置的两两比较, 若次序相反就交换. 第二趟排序结束, 此时第二个元素为次小
3. 以此类推...

双向冒泡排序: 交替改变扫描方向.

1. 第一趟从下往上扫描, 小者上浮到第一个位置
2. 第二趟从第二个位置往下扫描, 大者下沉到最后一个位置
3. 以此类推...

快速排序 (划分交换排序): 改进冒泡排序, 从两端向中间进行, 记录每次移动距离从相邻位置变为移到较远位置

1. 设两个指针 i 和 j, 初值分别为 low 和 high. 设基准记录 x=R[i]
2. 从 j 位置向前扫描找到第一个关键字小于 x 的记录存入当前 i 位置, i 自增 1
3. 从 i 位置向后扫描找到第一个关键字大于 x 的记录存入当前 j 位置, j 自减 1
4. 重复上两步, 直到 i 等于 j. 此时 x 排到了适当位置, x 前所有记录为较小, x 后所有记录为较大
5. 上述步骤称为一次划分
6. 递归进行划分, 直到所有记录排到适当位置

选择排序

基本思想: 每趟在待排序记录中选出关键字最小的记录, 依次放到已排好序的记录序列的最后.

直接选择排序: 每次在无序区选出最小记录, 与无序区中第一个记录交换

1. 第一趟排序: 在所有记录中找出最小记录, 与第一个记录交换
2. 第二趟排序: 在剩下 n-1 个记录中找出最小记录, 与第二个记录交换
3. 以此类推, 进行 n-1 趟

堆排序

堆排序是一种树形选择排序, 是对直接选择排序的改进: 可以看出, 直接选择排序的每趟排序中, 有许多比较可能在前一趟排序已经做过, 但是当时没有将结果保存下来. 堆排序则利用树形排序克服这一点.

基本思想: 把记录数组看成一颗完全二叉树的顺序存储结构, 利用双亲和孩子结点内在关系, 在无序区选择最大(小)记录.

堆: 对于一颗完全二叉树:

• 每个结点都比它的孩子结点大, 即为大根堆
• 每个结点都比它的孩子结点小, 即为小根堆

建(大根)堆过程 (筛选法): 较小记录逐层筛下去, 较大记录逐层选上来.

1. 将记录数组 R[1..n] (注意, 从 1 开始) 看成一颗完全二叉树顺序存储结构. 则任意节点 i 的左孩子为 2i, 右孩子为 2i+1, 双亲为 i/2
2. 假如某一结点的左子树和右子树已经是堆, 只需将它两个孩子中较大者与它比较. 如果父结点较小, 则与较大孩子结点交换, 这样可能破坏下一级的堆, 于是继续用上述方法构造下一级的堆.

如, 给定数组:

array	45	36	72	18	53	31	48	36
index	1	2	3	4	5	6	7	8

将其视为如下二叉树:

			45
		   /   \
		  36    72
		 / \    / \
		18 53  31 48
	   /
	  36

因结点数 n=8, 故从 ⌊n/2⌋=4 为根的子树开始调整 (想想为什么?), 如下图:

堆排序正是利用大根堆 (或小根堆) 来选取当前无序区中最大 (或最小) 记录实现排序的:

1. 将当前无序区 R[1..n] 以 R[1] 为根, 调整为一个大根堆
2. 将最大的堆顶记录和无序区最后一个记录交换, 则把最大值排到了最后. 此时无序区变为 R[1..n-1]
3. 在新的无序区中, 重复上述建堆和交换过程共 n-1 次

可以看出:

• 为了完成从小到大排序, 选择排序通过选取最小记录, 而堆排序通过选取最大记录进行交换, 刚好相反.
• 堆排序就是一个不断建堆的过程

归并排序

基本思想: 反复将两个有序的子文件两两归并, 得到更大的有序子文件.

二路归并排序

1. 将待排序文件看成 n 个长度为 1 的有序子文件, 将这些子文件两两归并. 得到 n/2 个长度为 2 的有序子文件
2. 将这 n/2 个子文件两两归并. 得到 n/4 个长度为 4 的有序子文件
3. 如此反复

分配排序

前面所述排序算法都基于关键字的比较. 理论上已经证明, 基于比较的排序, 至少需要 nlogn 次比较. 有不需要比较的排序方法, 可使时间复杂度降为一线性阶 O(n). 分配排序即一种不基于比较的排序算法.

箱排序: 依次扫描并根据关键字对应的位置装箱, 然后连到一起

抽象算法描述如下:

// 设关键字取值范围是 0..m-1
// 设 B[0..m-1] 是一个记录数组, 它的每一个分量都是一个链队列, 代表一个箱子
// 关键字相等的记录都放入同一个箱子代表的队列中.
// B[i].f 和 B[i].e 分别表示该队列的头指针和尾指针
void BinSort(SeqList R, int n) {
    // 置空所有链队列
    for (i = 0; i < m; i++) {
        InitQueue(B[i]);
    }
    // 分配, 装箱
    for (i = 0; i < n; i++) {
        k = R[i].key;
        EnQueue(B[k], R[i]);
    }
    i = 0;
    while (Empty(B[i])) { // 找到第一个非空箱子
        i++;
    }
    p = B[i].f;           // p 指向排序后的第一个记录
    for (j = i+1; j < m; j++) {
        if (! Empty(B[i])) {
            // 将所指向记录链接到上一个非空箱子的尾指针所指向的结点之后
        }
    }
}

基数排序: 对关键字分解, 对分量进行多趟箱排序

1. 假如要排序文件为: {36, 25, 48, 10, 6}
2. 对记录进行分解, 可知每个位数取值范围为 0..9, 只需设置 10 个箱子. 即 基数 为 10.
3. 先对个位数进行箱排序, 得到 [10], [25], [36, 6], [48]
4. 再对十位数进行箱排序, 得到 [6], [10], [25], [36], [48]

它是对箱排序的改进和推广, 解决了箱排序的空间浪费问题.

各种排序方法对比

排序			时间复杂度		空间复杂度	是否稳定	说明
----------------------------------------------------------------------------
直接插入		n^2				1			Y
希尔			!nlogn/n^1.25	1			N
冒泡			n^2				1			Y
快速			nlogn			logn		N
直接选择		n^2				1			N
堆			nlogn			1			N
归并			nlogn			n			Y
基数			d*(rd+n)		n+rd		Y		(rd:基数, d:关键字位数)

排序方法的选择:

• n 较小: 插入或选择
• n 较大: 快速, 堆, 归并
• 基本有序: 直接插入, 冒泡排序
• n 很大, 关键字位数小: 链式基数排序