第 9 章排序

Sorting

排序问题

给定 \(n\) 个对象：

\[ R[0],R[1],\ldots,R[n-1] \]

根据关键码 key，把它们重新排列为非递减或非递增序列。

排序是算法课程中最重要的基础主题之一，因为它集中体现：

比较与移动
分治
数据结构辅助
稳定性
空间与时间权衡
输入分布对性能的影响

学习目标

掌握排序的稳定性、内排序、外排序和评价维度
掌握直接插入排序、折半插入排序、希尔排序
掌握冒泡排序和快速排序
掌握直接选择排序、锦标赛排序和堆排序
掌握归并排序和链表归并排序
理解基数排序的思想
能比较各类排序算法的时间、空间、稳定性和适用场景

排序评价维度

维度	含义
比较次数	key 之间比较的次数
移动次数	记录移动或交换次数
时间复杂度	最好、最坏、平均
空间复杂度	是否需要额外数组或递归栈
稳定性	相等 key 的相对顺序是否保持
原地性	是否只使用 \(O(1)\) 或少量额外空间
输入敏感性	是否利用已有有序性

稳定性

若两个对象 key 相等，排序前后它们的相对顺序保持不变，则排序算法稳定。

例如：

\[ 25_a,\ 18,\ 25_b,\ 10 \]

稳定排序后：

\[ 10,\ 18,\ 25_a,\ 25_b \]

不稳定排序可能得到：

\[ 10,\ 18,\ 25_b,\ 25_a \]

内排序与外排序

内排序：所有待排序记录都能放入内存。

外排序：数据规模超过内存，需要访问外存。

本章主要讨论内排序。

外排序的核心通常是多路归并和缓冲区管理。

工程连接：排序库如何选择算法

真实系统通常不会只使用一种排序思想。

C++ STL std::sort 常用 introsort 结合快排、堆排和插入排序

Python Timsort 利用已有有序 run，适合真实业务数据

PostgreSQL 外排序和 Top-N 排序会结合内存、磁盘与执行计划

系统工具 大文件排序依赖分块、缓冲区和多路归并

因此本章不仅比较渐近复杂度，也要比较稳定性、额外空间、cache locality、递归深度和输入分布。

路线图

数据表抽象

排序对象通常包含：

key：用于比较
other data：随 key 一起移动的记录内容

template <class Key, class Value>
struct Record {
  Key key;
  Value value;
};

排序时不能只移动 key，否则记录内容会错位。

直接插入排序思想

第 \(i\) 轮开始时：

\[ R[0],R[1],\ldots,R[i-1] \]

已经有序。

把 \(R[i]\) 插入到前面有序区间的合适位置。

插入过程类似整理扑克牌。

直接插入排序代码

template <class T>
void insertionSort(std::vector<T>& a) {
  for (int i = 1; i < static_cast<int>(a.size()); ++i) {
    T temp = a[i];
    int j = i;
    while (j > 0 && temp < a[j - 1]) {
      a[j] = a[j - 1];
      --j;
    }
    a[j] = temp;
  }
}

元素向后移动，空位出现后插入 temp。

直接插入排序分析

最好情况：输入已经有序。

比较次数：

\[ n-1 \]

移动次数很少。

最坏情况：输入逆序。

比较次数：

\[ 1+2+\cdots+(n-1)=\frac{n(n-1)}{2} \]

时间复杂度 \(O(n^2)\)。

直接插入排序稳定。

平均情况

第 \(i\) 个元素可能插入到前面 \(i+1\) 个位置之一。

平均移动和比较次数与 \(i\) 成正比。

总复杂度：

\[ O(n^2) \]

直接插入排序适合小规模或基本有序数据。

折半插入排序

折半插入排序用二分查找确定插入位置。

它减少比较次数，但不能减少移动次数。

template <class T>
void binaryInsertionSort(std::vector<T>& a) {
  for (int i = 1; i < static_cast<int>(a.size()); ++i) {
    T temp = a[i];
    int left = 0, right = i - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (temp < a[mid]) right = mid - 1;
      else left = mid + 1;
    }
    for (int j = i - 1; j >= left; --j) a[j + 1] = a[j];
    a[left] = temp;
  }
}

折半插入排序分析

插入第 \(i\) 个元素时，二分查找比较次数约为：

\[ \lfloor \log_2 i\rfloor + 1 \]

但移动仍可能是 \(O(i)\)。

所以总时间复杂度仍为：

\[ O(n^2) \]

优势主要是减少昂贵 key 比较。

希尔排序

希尔排序思想

希尔排序又称缩小增量排序。

思想：

选定增量序列
对间隔为 gap 的子序列做插入排序
gap 逐渐缩小
最后 gap=1，完成整体插入排序

希尔排序让元素可以一次跨越较长距离。

希尔排序代码

template <class T>
void shellSort(std::vector<T>& a) {
  for (int gap = a.size() / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < static_cast<int>(a.size()); ++i) {
      T temp = a[i];
      int j = i;
      while (j >= gap && temp < a[j - gap]) {
        a[j] = a[j - gap];
        j -= gap;
      }
      a[j] = temp;
    }
  }
}

不同增量序列会显著影响性能。

冒泡排序

冒泡排序代码

冒泡排序反复比较相邻元素，若逆序则交换。

每一趟把当前最大元素“冒”到右侧。

template <class T>
void bubbleSort(std::vector<T>& a) {
  for (int pass = a.size() - 1; pass > 0; --pass) {
    bool swapped = false;
    for (int i = 0; i < pass; ++i) {
      if (a[i + 1] < a[i]) {
        std::swap(a[i], a[i + 1]);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}

冒泡排序稳定，但通常效率较低。

快速排序思想

快速排序递归结构

快速排序使用分治：

选择 pivot
将小于 pivot 的元素放左边
将大于 pivot 的元素放右边
递归排序左右子区间

平均复杂度：

\[ O(n\log n) \]

最坏复杂度：

\[ O(n^2) \]

快速排序 partition

template <class T>
int partition(std::vector<T>& a, int left, int right) {
  T pivot = a[right];
  int i = left;
  for (int j = left; j < right; ++j) {
    if (a[j] < pivot) {
      std::swap(a[i], a[j]);
      ++i;
    }
  }
  std::swap(a[i], a[right]);
  return i;
}

partition 完成后，pivot 位于最终位置。

快速排序代码

template <class T>
void quickSort(std::vector<T>& a, int left, int right) {
  if (left >= right) return;
  int pivot = partition(a, left, right);
  quickSort(a, left, pivot - 1);
  quickSort(a, pivot + 1, right);
}

工程实现常加入：

三数取中
小数组转插入排序
随机 pivot
尾递归优化

快速排序分析

理想情况下每次近似二分：

\[ T(n)=2T(n/2)+O(n)=O(n\log n) \]

极端情况下每次只划掉一个元素：

\[ T(n)=T(n-1)+O(n)=O(n^2) \]

快速排序通常不稳定。

直接选择排序

直接选择排序代码

第 \(i\) 趟从未排序区间中选出最小元素，放到位置 \(i\)。

template <class T>
void selectionSort(std::vector<T>& a) {
  for (int i = 0; i < static_cast<int>(a.size()); ++i) {
    int minIndex = i;
    for (int j = i + 1; j < static_cast<int>(a.size()); ++j) {
      if (a[j] < a[minIndex]) minIndex = j;
    }
    std::swap(a[i], a[minIndex]);
  }
}

比较次数固定为 \(O(n^2)\)。

直接选择排序通常不稳定。

锦标赛排序

锦标赛排序用树形比较记录胜者。

优点：

避免重复比较
可较快找到最小值、次小值等

缺点：

需要额外空间保存比较树
实现复杂度高于直接选择排序

它体现了“保存比较历史”这一思想。

堆排序

堆排序使用最大堆。

流程：

Floyd 建堆
交换堆顶和堆尾
堆大小减一
对根下滤
重复直到有序

复杂度：

\[ O(n\log n) \]

堆排序原地但不稳定。

堆排序代码

template <class T>
void heapSort(std::vector<T>& a) {
  std::make_heap(a.begin(), a.end());
  for (auto end = a.end(); end != a.begin(); --end) {
    std::pop_heap(a.begin(), end);
  }
}

std::make_heap 建最大堆。

std::pop_heap 把当前最大元素放到末尾。

归并排序思想

归并排序递归结构

归并排序也是分治：

把序列分成左右两半
分别排序
合并两个有序序列

归并排序稳定。

时间复杂度稳定为：

\[ O(n\log n) \]

数组归并需要 \(O(n)\) 额外空间。

合并两个有序区间

template <class T>
void merge(std::vector<T>& a, std::vector<T>& tmp,
           int left, int mid, int right) {
  int i = left, j = mid + 1, k = left;
  while (i <= mid && j <= right) {
    if (a[i] <= a[j]) tmp[k++] = a[i++];
    else tmp[k++] = a[j++];
  }
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= right) tmp[k++] = a[j++];
  for (int p = left; p <= right; ++p) a[p] = tmp[p];
}

相等时优先取左边元素，保证稳定性。

递归归并排序

template <class T>
void mergeSort(std::vector<T>& a, std::vector<T>& tmp,
               int left, int right) {
  if (left >= right) return;
  int mid = left + (right - left) / 2;
  mergeSort(a, tmp, left, mid);
  mergeSort(a, tmp, mid + 1, right);
  merge(a, tmp, left, mid, right);
}

递归深度为 \(O(\log n)\)。

每一层合并总成本为 \(O(n)\)。

迭代归并排序

迭代归并从长度 1 的有序段开始：

\[ [1]\to[2]\to[4]\to[8]\to\cdots \]

每一趟把相邻的两个有序段合并为更长的有序段。

迭代版避免递归调用，但仍需要辅助数组。

链表归并排序

链表不适合随机访问，但适合归并。

优势：

合并时只改指针
不需要移动记录
可以稳定排序

链表归并排序常用于链表结构的高效排序。

基数排序

基数排序思想

基数排序不是比较排序。

它按照关键码的各位进行分配和收集。

例如十进制整数可按个位、十位、百位依次稳定分配。

若关键码位数为 \(d\)，基数为 \(r\)，元素数为 \(n\)：

\[ O(d(n+r)) \]

适合定长整数或字符串。

比较排序的下界

只通过“两两比较”决定顺序的排序算法，都可以看成一棵决策树。

每个内部结点是一场比较
每条边表示比较结果
每个叶子对应一种可能的排列

长度为 \(n\) 的输入共有 \(n!\) 种排列，因此决策树至少需要 \(n!\) 个叶子。

若最坏比较次数为 \(h\)，二叉决策树最多有 \(2^h\) 个叶子，所以：

\[ 2^h \ge n! \]

因此：

\[ h \ge \log_2(n!)=\Omega(n\log n) \]

这说明快速排序、堆排序和归并排序达到的 \(O(n\log n)\) 已经是比较排序的渐近最优量级。

非比较排序，例如计数排序、桶排序和基数排序，可以利用 key 的取值范围或位结构绕开这个下界。

排序算法总表

算法	最好	平均	最坏	空间	稳定
直接插入	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	是
折半插入	\(O(n\log n)\) 比较	\(O(n^2)\) 移动	\(O(n^2)\)	\(O(1)\)	是
希尔	依增量	依增量	通常低于 \(O(n^2)\)	\(O(1)\)	否
冒泡	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	是
快速	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n^2)\)	\(O(\log n)\)	否
选择	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	否
堆排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(1)\)	否
归并	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n)\)	是
基数	\(O(d(n+r))\)	\(O(d(n+r))\)	\(O(d(n+r))\)	\(O(n+r)\)	是

如何选择排序算法

场景	推荐
小数组或基本有序	插入排序
通用内存排序	快速排序或 introsort
需要稳定性	归并排序
空间受限且不要求稳定	堆排序
链表排序	归并排序
整数 key 范围/位数受限	计数/基数排序
只取 Top-K	堆

练习 1：插入排序

对序列：

\[ 3,1,4,1,5,9,2,6,5 \]

使用直接插入排序。

关键过程：

插入 1：1,3,4,1,5,9,2,6,5
插入第二个 1：1,1,3,4,5,9,2,6,5
插入 2：1,1,2,3,4,5,9,6,5
插入 6：1,1,2,3,4,5,6,9,5
插入 5：1,1,2,3,4,5,5,6,9

练习 2：第二趟排序结果判断

序列：

\[ 11,12,13,7,8,9,23,4,5 \]

若它是某种排序第二趟后的结果，最符合插入排序。

原因：插入排序第二趟只保证前三个元素已经有序，而后面部分可保持原始相对状态。

冒泡、选择、归并在第二趟后会呈现不同的局部结构。

练习 3：归并排序

对：

\[ 3,1,4,1,5,9,2,6 \]

归并排序分解：

\[ [3,1,4,1]\ [5,9,2,6] \]

继续分解到单元素后合并：

\[ [1,3]\ [1,4]\ [5,9]\ [2,6] \]

再合并：

\[ [1,1,3,4]\ [2,5,6,9] \]

最终：

\[ [1,1,2,3,4,5,6,9] \]

练习 4：堆排序稳定性

堆排序不稳定。

原因：

堆调整会让元素在树中跨层交换。

相等 key 的记录可能因为与其他元素交换而改变相对顺序。

因此，即使比较时不交换相等 key，也无法保证整体稳定。

第 9 章 排序

排序问题

学习目标

排序评价维度

稳定性

内排序与外排序

工程连接：排序库如何选择算法

路线图

数据表抽象

直接插入排序思想

直接插入排序代码

直接插入排序分析

平均情况

折半插入排序

折半插入排序分析

希尔排序

希尔排序思想

希尔排序代码

冒泡排序

冒泡排序代码

快速排序思想

快速排序递归结构

快速排序 partition

快速排序代码

快速排序分析

直接选择排序

直接选择排序代码

锦标赛排序

堆排序

堆排序代码

归并排序思想

归并排序递归结构

合并两个有序区间

递归归并排序

迭代归并排序

链表归并排序

基数排序

基数排序思想

比较排序的下界

排序算法总表

如何选择排序算法

练习 1：插入排序

练习 2：第二趟排序结果判断

练习 3：归并排序

练习 4：堆排序稳定性

第 9 章排序