八、排序

本章导览

共 9 个小节：插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、外部排序

本章重点

• 排序看时间复杂度 + 稳定性 + 场景
• 内部：插入（直接 / 希尔）、选择（简单 / 堆）、交换（冒泡 / 快速）、归并、基数
• 记牢：快排最坏 O(n²)、堆排不稳定

插入排序

关键点

• 像理牌，插入已排序区；O(n²)，基本有序时 O(n)
• 稳定；宜小规模 / 基本有序

希尔排序

关键点

• 缩小增量、分组插入，突破 O(n²) 到约 O(n^1.3)
• 不稳定（跳跃移动）；增量序列影响效率

冒泡排序

关键点

• 相邻比较交换，大数下沉；O(n²)，有序 + 标志可 O(n)
• 稳定；可加「无交换则提前终止」

快速排序

关键点

• 分治 + Partition（左 ≤ pivot ≤ 右）；平均 O(n log n)（最快）
• 划分不均最坏 O(n²)；不稳定
• 三数取中 / 随机 pivot 避免最坏

简单选择排序

关键点

• 每趟选最值放前面；恒 O(n²)（最好最坏一样）
• 不稳定；交换次数少

堆排序

关键点

• 大顶堆（升序）/ 小顶堆（降序）；建堆 + 反复取堆顶
• O(n log n)、原地、不稳定

归并排序

关键点

• 分治：二分 + 二路归并；恒 O(n log n) 且稳定
• 需 O(n) 辅助空间；是外部排序的核心

基数排序

关键点

• 非比较排序，按位分配收集（LSD 最低位优先）
• O(d(n+r))、稳定，需桶空间；宜位数少的整数

外部排序

关键点

• 核心是减少磁盘 I/O；多路归并
• 优化：败者树（选最小）、置换选择（更长归并段）、最佳归并树（哈夫曼定归并顺序）

归并排序

败者树

置换—选择算法

最佳归并树