Mdr-C-Tutorial

主题

排序算法 ​

1. 引言 ​

1.1 排序的定义与重要性 ​

1.2 排序算法的分类 ​

1.3 评价标准 ​

1.3.1 时间复杂度 ​

1.3.2 空间复杂度 ​

1.3.3 稳定性 ​

1.3.4 原地排序 ​

2. 简单排序算法 ​

2.1 冒泡排序（Bubble Sort） ​

2.1.1 算法原理 ​

2.1.2 算法实现 ​

2.1.3 复杂度分析 ​

2.1.4 优化方案 ​

2.2 选择排序（Selection Sort） ​

2.2.1 算法原理 ​

2.2.2 算法实现 ​

2.2.3 复杂度分析 ​

2.3 插入排序（Insertion Sort） ​

2.3.1 算法原理 ​

2.3.2 算法实现 ​

2.3.3 复杂度分析 ​

2.3.4 二分插入排序 ​

2.4 希尔排序（Shell Sort） ​

2.4.1 算法原理 ​

2.4.2 算法实现 ​

2.4.3 复杂度分析 ​

3. 高效排序算法 ​

3.1 归并排序（Merge Sort） ​

3.1.1 分治思想 ​

3.1.2 算法实现 ​

3.1.3 复杂度分析 ​

3.1.4 空间优化 ​

3.2 快速排序（Quick Sort） ​

3.2.1 分治思想 ​

3.2.2 分区操作 ​

3.2.3 算法实现 ​

3.2.4 复杂度分析 ​

3.2.5 随机化快排 ​

3.2.6 三路快排 ​

3.3 堆排序（Heap Sort） ​

3.3.1 堆的概念 ​

3.3.2 堆的构建 ​

3.3.3 算法实现 ​

3.3.4 复杂度分析 ​

4. 特殊排序算法 ​

4.1 计数排序（Counting Sort） ​

4.1.1 算法原理 ​

4.1.2 算法实现 ​

4.1.3 适用场景 ​

4.1.4 复杂度分析 ​

4.2 基数排序（Radix Sort） ​

4.2.1 算法原理 ​

4.2.2 LSD 与 MSD ​

4.2.3 算法实现 ​

4.2.4 复杂度分析 ​

4.3 桶排序（Bucket Sort） ​

4.3.1 算法原理 ​

4.3.2 算法实现 ​

4.3.3 复杂度分析 ​

4.3.4 与其他排序的结合 ​

5. 排序算法的理论分析 ​

5.1 比较排序的下界 ​

5.1.1 决策树模型 ​

5.1.2 信息论角度 ​

5.1.3 下界证明 ​

5.2 排序算法的稳定性分析 ​

5.3 自适应排序与有序性度量 ​

5.4 排序算法的实际性能比较 ​

6. 排序算法的应用与变种 ​

6.1 外部排序 ​

6.1.1 多路归并 ​

6.1.2 置换选择 ​

6.2 字符串排序 ​

6.2.1 三向字符串快排 ​

6.2.2 MSD 字符串排序 ​

6.3 部分排序问题 ​

6.3.1 Top-K 问题 ​

6.3.2 第 K 小元素 ​

6.4 动态排序问题 ​

6.4.1 动态排序与数据结构 ​

7. 实际应用与优化 ​

7.1 混合排序算法 ​

7.1.1 Introsort ​

7.1.2 Timsort ​

7.2 并行排序 ​

习题 ​

  1. [M4.5**] 比较排序算法的下界：

    证明：任何基于比较的排序算法（即仅通过比较元素来确定顺序），在最坏情况下都需要 Ω(nlg⁡n) 次比较来排序 n 个不同的元素。 提示：考虑决策树模型。每个内部节点代表一次比较，叶子节点代表一种可能的排序结果。树的高度对应最坏情况下的比较次数。分析叶子节点的数量和树的高度之间的关系。

  2. 探究希尔排序。第 3.5.6. 问查阅资料即可，第 7. 问是截至目前计算机科学界的未解难题。

    (1) [2.1] 希尔排序通过一系列递减的增量（例如，h = {..., 13, 4, 1}）对数组进行多轮“h-排序”。请从概念上解释，为什么这种“分组预排序”的策略，通常会比直接进行一次完整的插入排序（即只有增量为 1）更有效率？

    (2) [M4.4] 考虑希尔本人提出的原始增量序列 h = {..., n/4, n/2, 1}（其中 n 为 2 的幂）。请分析并证明，在使用此序列时，希尔排序的最坏情况时间复杂度为 Θ(n²)。（提示：构造一个最坏情况的数组。例如，数组的前一半填充较大的数，后一半填充较小的数。分析当增量 h > 1 时，元素是否能在数组的两半之间有效移动。）

    为了克服 Θ(n²) 的最坏情况，研究者们提出了许多更优的增量序列。

    (3) [HM7.7**] Hibbard 序列是形如 2^k - 1 的序列 ({..., 15, 7, 3, 1})。证明：它的时间复杂度为 O(n32)。

    (4) [HM7.8**] Knuth 序列是形如 (3^k - 1) / 2 的序列 ({..., 40, 13, 4, 1})。证明：它的时间复杂度为 O(n32)。

    (5) [2.1] Hibbard 序列和 Kunth 序列的时间复杂度相同。哪个更具优越性？

    (6) [HM9.9**] Sedgewick 序列是形如 4^k + 3*2^(k-1) + 1 的序列 ({..., 109, 41, 19, 5, 1})。证明：它的时间复杂度为 O(n43)。

    (7) [HM10.10**] 最好的增量序列是什么？希尔排序的确切的时间复杂度下界是什么？