2. 折半插入排序

有序区内用折半查找定位插入位置，减少比较次数（仍为 O(log n) 定位+O(n) 移动）；移动次数不变，总体仍 O(n²)。

3. 希尔排序（缩小增量排序）

按增量 d_k 将表分组，组内直接插入；逐步缩小 d（如 d₁=n/2, d_{k+1}=⌊d_k/2⌋）直至 d=1。时间约 O(n^1.3)；不稳定。

8.3 交换排序

1. 冒泡排序

每趟两两比较相邻记录，将最大/最小者"冒泡"到一端。某趟无交换即可提前结束。

• 最好 O(n)，平均/最坏 O(n²)；稳定。

2. 快速排序（Hoare 划分）

选基准 pivot，一趟划分出两区间：左 ≤ pivot ≤ 右，递归子区间。

• 平均 O(n log n)，最坏 O(n²)（基本有序时退化）。
• 空间 O(log n)~O(n)（递归栈）；不稳定。
• 快速排序是内部排序中平均性能最优的算法。

int Partition(int a[],int low,int high){
  int pivot=a[low];
  while(lowwhile(low=pivot) high--;
    a[low]=a[high];
    while(lowreturn low;
}
void QuickSort(int a[],int low,int high){
  if(lowint p=Partition(a,low,high);
    QuickSort(a,low,p-1); QuickSort(a,p+1,high);
  }
}

8.4 选择排序

1. 简单选择排序

每趟从无序区选出最小记录与无序区首元素交换。比较次数恒为 n(n-1)/2；移动次数少。O(n²)，不稳定。

2. 堆排序

• 大根堆：a[i] ≥ a[2i] 且 a[i] ≥ a[2i+1]（升序用大根堆；降序用小根堆）。
• 建堆：⌊n/2⌋ 的结点开始向下调整，O(n)。
• 每趟堆顶与末尾交换，堆规模 −1 再向下调整。总 O(n log n)；不稳定；空间 O(1)。
• 适合选取"前 k 大/小"的题目。

8.5 归并排序

二路归并：将相邻两有序表合成一个；递归或迭代（非递归更省空间）实现。时间恒 O(n log n)；稳定；空间 O(n)。

8.6 基数排序

基于多关键字分配-收集：按低位→高位（LSD）或高位→低位（MSD），每趟分配到 r 个队列再依次收集。O(d(n+r))；稳定；空间 O(r)。

8.7 外部排序简介

• 基本方法：归并路数 k 越大趟数越少；k 路平衡归并。
• 败者树：在 k 个归并段中取最小者仅需 ⌈log₂k⌉ 次比较，与 k 无关。
• 置换-选择排序：在内存工作区容量 m 时生成平均长度为 2m 的初始归并段。
• 最佳归并树（哈夫曼思想）：k 叉哈夫曼树，使总 I/O 最少；空缺补"虚段"。

8.8 各类排序比较

8.9 外部排序动画演示

当数据量超过内存容量时需要外部排序。核心是 多路归并 减少I/O次数, 用 败者树 选出最小关键字, 置换-选择排序 生成更长的初始归并段。