排序

这一页整理 Ch06 Sorting。重点是比较排序的前提、插入排序、逆序对与简单排序下界、Shellsort、Heapsort 和 Mergesort。

1. 排序问题的前提

课件讨论的是 comparison-based sorting，也就是基于比较的排序。

基本假设：

• 输入存在数组 A[] 中。
• 有 N 个元素，N 是合法整数。
• 元素之间可以用 < 和 > 比较。
• 只讨论 internal sorting，也就是整个排序过程都在主存中完成。

通用函数形式可以理解成：

void X_Sort(ElementType A[], int N);

排序的目标是把数组变成非降序：

A[0] <= A[1] <= ... <= A[N - 1]

2. 插入排序 Insertion Sort

插入排序的直觉很像整理扑克牌：

左边已经有序，右边还没处理。
每次拿右边第一个元素，插入到左边有序部分的正确位置。

例如：

原数组:  34  8  64  51  32  21

先看 34: [34] 8 64 51 32 21
插入 8: [8 34] 64 51 32 21
插入 64: [8 34 64] 51 32 21
插入 51: [8 34 51 64] 32 21
...

3. 插入排序代码

课件中的代码整理如下：

void InsertionSort(ElementType A[], int N) {
    int j, P;
    ElementType Tmp;

    for (P = 1; P < N; P++) {
        Tmp = A[P];

        for (j = P; j > 0 && A[j - 1] > Tmp; j--) {
            A[j] = A[j - 1];
        }

        A[j] = Tmp;
    }
}

变量含义：

• P：当前要插入的新元素位置。
• Tmp：保存新来的元素。
• j：在有序区中从右往左找插入位置。

内层循环做两件事：

1. 只要左边元素比 Tmp 大，就把它向右移动一格。
2. 找到第一个不大于 Tmp 的位置后，把 Tmp 放进去。

可视化：

插入 32:

8 34 51 64 32 21
        ↑  ↑
       64 右移

8 34 51 64 64 21
     ↑  ↑
    51 右移

8 34 51 51 64 21
  ↑  ↑
 34 右移

8 32 34 51 64 21

4. 插入排序复杂度

最好情况：数组本来就是有序的。

每一轮只比较一次，不需要移动很多元素
T(N) = O(N)

最坏情况：数组是逆序的。

每个新元素都要一路移动到最前面
T(N) = O(N^2)

更细一点看，插入排序的运行时间和原数组的“乱序程度”有关。
如果数组几乎有序，插入排序会很快。

5. 逆序对 Inversion

逆序对定义：

i < j 但 A[i] > A[j]

也就是前面的元素比后面的元素大，违反了递增顺序。

例子：

34, 8, 64, 51, 32, 21

逆序对有：

(34, 8)
(34, 32)
(34, 21)
(64, 51)
(64, 32)
(64, 21)
(51, 32)
(51, 21)
(32, 21)

一共 9 个。

插入排序中，每次相邻元素交换或移动，本质上是在消掉逆序对。
因此如果原数组有 I 个逆序对，插入排序可以写成：

T(N, I) = O(N + I)

这解释了为什么插入排序适合 almost sorted 的数组：
如果 I 很小，它接近线性时间。

6. 简单排序算法的下界

课件给出两个重要结论。

第一个：

N 个互异元素的数组，平均逆序对数量是 N(N - 1) / 4

第二个：

任何只通过交换相邻逆序元素来排序的算法，平均需要 Ω(N^2) 时间

原因是：

交换一对相邻的错位元素，正好只消掉一个逆序对。

平均逆序对数量是二次级别，所以只靠相邻交换的简单排序不可能平均快过 Ω(N^2)。

想更快，就必须让元素一次跨过较长距离，例如 Shellsort；或者用更强的结构和分治思想，例如 Heapsort、Mergesort。

7. Shellsort 的基本思想

Shellsort 是 Donald Shell 提出的排序算法。
它可以看成“带间隔的插入排序”。

普通插入排序每次只比较相邻位置。
Shellsort 先让距离较远的元素也能交换，快速减少大量逆序。

核心概念是 h-sort：

如果对每个 i，都有 A[i] <= A[i + h]，
那么数组就是 h-sorted。

实际操作时，是把下标相差 h 的元素分组，并对每组做插入排序。

例如增量序列：

5, 3, 1

排序过程就是：

先做 5-sort
再做 3-sort
最后做 1-sort

最后的 1-sort 就是普通插入排序，因此一定能得到完全有序数组。

一个重要性质：

一个 h_k-sorted 的文件，再经过 h_{k-1}-sort 后，仍然保持 h_k-sorted。

也就是说，前面较大间隔建立起来的有序性不会被后续较小间隔破坏。

8. Shellsort 代码

课件使用 Shell 的原始增量：

h_t = floor(N / 2)
h_k = floor(h_{k+1} / 2)

也就是：

N/2, N/4, N/8, ..., 1

代码整理如下：

void Shellsort(ElementType A[], int N) {
    int i, j, Increment;
    ElementType Tmp;

    for (Increment = N / 2; Increment > 0; Increment /= 2) {
        for (i = Increment; i < N; i++) {
            Tmp = A[i];

            for (j = i; j >= Increment; j -= Increment) {
                if (Tmp < A[j - Increment]) {
                    A[j] = A[j - Increment];
                } else {
                    break;
                }
            }

            A[j] = Tmp;
        }
    }
}

可以把内层看成：

在间隔为 Increment 的子序列上做插入排序。

9. Shellsort 复杂度和增量序列

Shellsort 的复杂度强烈依赖增量序列。

Shell 原始增量

N/2, N/4, ..., 1

最坏情况：

Θ(N^2)

课件中坏例子的核心原因是：
相邻增量不一定互质，较小增量可能对前面已经形成的结构帮助很有限。

Hibbard 增量

Hibbard increment sequence：

h_k = 2^k - 1

例如：

1, 3, 7, 15, 31, ...

特点是连续增量没有公因子。
使用 Hibbard 增量时，Shellsort 最坏复杂度是：

Θ(N^{3/2})

Sedgewick 增量

课件提到 Sedgewick 的一个优秀序列：

1, 5, 19, 41, 109, ...

相关结论：

Tavg(N) = O(N^{7/6})
Tworst(N) = O(N^{4/3})

考点上不一定要背完整生成式，但要知道：

Shellsort 简单，但分析很复杂；增量序列会显著影响复杂度。

10. Heapsort 思路一：用堆不断 DeleteMin

第一种写法最直接：

1. BuildHeap(H)
2. 重复 N 次 DeleteMin(H)，依次放入临时数组
3. 把临时数组复制回原数组

复杂度：

BuildHeap: O(N)
N 次 DeleteMin: N * O(log N)
总时间: O(N log N)

缺点：

需要额外开一个 TmpH 数组，空间翻倍。

所以课件接着给出原地版本。

11. Heapsort 原地版本

原地 Heapsort 通常使用 max heap。

思路：

1. 把数组原地建成 max heap。
2. 堆顶 A[0] 是当前最大值。
3. 把 A[0] 和最后一个未排序位置交换。
4. 未排序区长度减 1，对新的 A[0] 做 PercDown。
5. 重复直到排序完成。

代码框架：

void Heapsort(ElementType A[], int N) {
    int i;

    for (i = N / 2; i >= 0; i--) {
        PercDown(A, i, N);
    }

    for (i = N - 1; i > 0; i--) {
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}

注意这里数据从数组下标 0 开始。
如果使用课件前面优先队列常见的 1 起始堆，下标公式会不同。

复杂度：

BuildHeap: O(N)
每次 DeleteMax/PercDown: O(log N)
总时间: O(N log N)
额外空间: O(1)

课件结论：Heapsort 平均比较次数大约是：

2N log N - O(N log log N)

但实践中，它常常比使用好增量序列的 Shellsort 慢一些。

12. 归并两个有序表

Mergesort 的核心操作是 merge：把两个已经有序的表合并成一个有序表。

例子：

A: 1 13 24 26
B: 2 15 27 38

合并结果:
C: 1 2 13 15 24 26 27 38

做法：

1. Aptr 指向 A 当前最小未合并元素。
2. Bptr 指向 B 当前最小未合并元素。
3. 比较 A[Aptr] 和 B[Bptr]，较小者放进 C。
4. 对应指针后移。
5. 某一边用完后，把另一边剩余元素全部复制进 C。

每个元素只被处理一次，所以：

Merge 两个有序表: O(N)

其中 N 是两个表的总元素数。

13. Mergesort

归并排序使用分治：

1. 把数组分成左右两半。
2. 递归排序左半边。
3. 递归排序右半边。
4. 把两个有序半边 merge。

递归框架：

void MSort(ElementType A[], ElementType TmpArray[],
           int Left, int Right) {
    int Center;

    if (Left < Right) {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center + 1, Right);
        Merge(A, TmpArray, Left, Center + 1, Right);
    }
}

外层函数只申请一次临时数组：

void Mergesort(ElementType A[], int N) {
    ElementType *TmpArray;

    TmpArray = malloc(N * sizeof(ElementType));
    if (TmpArray != NULL) {
        MSort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    } else {
        FatalError("No space for tmp array!!!");
    }
}

为什么临时数组要在外层申请一次？

如果每次 Merge 都局部申请 TmpArray，
空间和申请释放开销都会变得很糟。

课件提示：如果每一层调用都局部声明临时数组，空间可能变成：

O(N log N)

正确做法是共用一个 TmpArray，额外空间：

O(N)

14. Merge 代码

课件代码整理如下：

void Merge(ElementType A[], ElementType TmpArray[],
           int Lpos, int Rpos, int RightEnd) {
    int i, LeftEnd, NumElements, TmpPos;

    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;

    while (Lpos <= LeftEnd && Rpos <= RightEnd) {
        if (A[Lpos] <= A[Rpos]) {
            TmpArray[TmpPos++] = A[Lpos++];
        } else {
            TmpArray[TmpPos++] = A[Rpos++];
        }
    }

    while (Lpos <= LeftEnd) {
        TmpArray[TmpPos++] = A[Lpos++];
    }

    while (Rpos <= RightEnd) {
        TmpArray[TmpPos++] = A[Rpos++];
    }

    for (i = 0; i < NumElements; i++, RightEnd--) {
        A[RightEnd] = TmpArray[RightEnd];
    }
}

最后从右往左复制回 A：

A[RightEnd] = TmpArray[RightEnd]

这样写是为了在 RightEnd 被逐步减小时，把本次 merge 的区间复制回原数组。

15. Mergesort 复杂度

递归式：

T(1) = 1
T(N) = 2T(N/2) + O(N)

展开：

T(N) = 2T(N/2) + O(N)
     = 2^k T(N/2^k) + k * O(N)

当：

N / 2^k = 1

有：

k = log N

所以：

T(N) = N * T(1) + log N * O(N)
     = O(N log N)

空间复杂度：

O(N)

因为需要线性大小的临时数组。

课件评价：

• Mergesort 需要额外线性空间。
• 数组复制有额外开销。
• 内部排序中不一定常用。
• 但它非常适合 external sorting。

16. 四种排序对比

排序	核心思想	平均/常见复杂度	最坏复杂度	额外空间
Insertion Sort	有序区中插入新元素	取决于逆序对，近乎有序时很快	O(N^2)	O(1)
Shellsort	多轮带间隔插入排序	依赖增量序列	Shell 原始增量 Θ(N^2)	O(1)
Heapsort	建堆后反复取最大/最小	O(N log N)	O(N log N)	原地版 O(1)
Mergesort	分治 + 线性 merge	O(N log N)	O(N log N)	O(N)

17. 考点速记

考点	必会内容
比较排序	只通过 < 和 > 比较输入元素
internal sorting	整个排序在主存中完成
插入排序最好	已经有序，O(N)
插入排序最坏	逆序，O(N^2)
逆序对	i < j 但 A[i] > A[j]
插入排序和逆序对	T(N, I) = O(N + I)
相邻交换下界	平均需要 Ω(N^2)
Shellsort	h-sort，最后一定要有 1-sort
Shell 原始增量	最坏 Θ(N^2)
Hibbard 增量	2^k - 1，最坏 Θ(N^{3/2})
Heapsort	BuildHeap + DeleteMax，O(N log N)
Mergesort	T(N)=2T(N/2)+O(N)，所以 O(N log N)
Mergesort 空间	需要 O(N) 额外数组

18. 易错点

• 插入排序的内层循环是“移动元素”，不是每次都真的交换两个元素。
• 插入排序最坏是逆序，最好是已经有序。
• 逆序对数量越少，插入排序越快。
• Shellsort 的最后一轮必须是 1-sort，否则不能保证完全有序。
• Shellsort 的复杂度不能只写一个固定结论，要看增量序列。
• Heapsort 原地版通常用 max heap，把最大值放到数组末尾。
• BuildHeap 是 O(N)，不是 O(N log N)。
• Mergesort 的 merge 是线性的。
• Mergesort 需要额外 O(N) 空间；如果每层都新建临时数组，会浪费更多空间。