排序算法

引言：排序不是把数字排好看

排序把一个序列重排为满足某个全序或严格弱序的序列。它表面上是“从小到大”，本质上却是在建立一个可利用的顺序结构：有序数组可用二分查找把查找缩到对数级；扫描相邻元素可识别重复、区间和相对次序；按键排序则是数据库、日志、索引与调度系统的公共底座。

选择排序算法时，不能只背一张 $O(n\log n)$ 表。数据是否近乎有序、键是否是有限范围整数、相等键能否保留原次序、是否能额外开数组、只要第 $K$ 小而不是完整排序，都会改变最优选择。本文从这些约束出发，给出常用排序的不变量、可直接编译的 C++ 模板，以及工程选型边界。

先建立坐标系：四个性质与一个下界

稳定、原地、适应与在线

设两个记录 a、b 的比较键相等，且 a 在输入中位于 b 前：

• 稳定（stable）：排序后仍保持 a 在 b 前。多关键字排序尤其依赖它：先按次关键字稳定排序，再按主关键字稳定排序，结果等价于按复合键排序。
• 原地（in-place）：除递归栈或常数个局部变量外，不随 $n$ 增长申请辅助存储。严格定义会讨论 $O(\log n)$ 栈空间；日常算法题通常把它与$O(n)$ 辅助数组区分即可。
• 适应（adaptive）：输入越接近有序，实际工作越少。插入排序的代价可写成$\Theta(n+I)$，其中 $I$ 是逆序对数；当 $I$ 很小，它接近线性。
• 在线（online）：可在读到前缀时处理，不必看完全部输入。插入排序可在线，归并、堆和通常的快速排序不是这个意义上的在线算法。

不要把“交换次数少”误认为稳定。选择排序每轮只交换一次，但最小值与前端元素交换时，可能跨过同键元素；稳定性取决于元素相等时是否发生跨越。

比较排序的 $\Omega(n\log n)$ 下界

只通过“比较两个元素谁小”的算法，面对 $n$ 个互异元素时必须区分 $n!$种排列。把一次比较看作决策树的二叉分支，树高至少满足

$$2^h \ge n!,\qquad h \ge \log_2(n!)=\Omega(n\log n).$$

因此归并、堆、快速排序的 $O(n\log n)$ 不是还差一个巧思，而是在比较模型中已经渐近最优。计数、桶和基数排序能线性或近线性，是因为它们利用了键为整数、值域有限或位数有限等额外信息，已经不在纯比较模型内。

排序后的单调性为何重要

升序数组满足谓词 a[i] >= target 从假到真的单调边界，因而能用二分查找定位第一个不小于目标的位置。无序数组没有这种单调性：比较中点后丢弃一半区间没有逻辑依据。排序花费$O(n\log n)$，随后每次查询花费 $O(\log n)$；当查询次数多时，预排序是典型的以空间局部性换吞吐的决策。

二次排序：小规模与近乎有序的可靠基线

这些算法的最坏时间均为 $O(n^2)$，但不应因此被一概否定。它们代码短、常数小、缓存友好，常被高性能排序用在很小的递归叶子上。

冒泡排序：把最大值逐轮送到末尾

第 pass 趟从左向右交换逆序相邻对后，区间末端已有 pass + 1 个最大元素。若一趟没有交换，整个未排序前缀已升序，可以提前结束；这使它对已排序输入为$O(n)$。稳定性来自只在 a[i] > a[i + 1] 时交换，代价是大量相邻交换。

#include <cstddef>
#include <utility>
#include <vector>

void bubbleSort(std::vector<int>& a) {
  for (std::size_t end = a.size(); end > 1; --end) {
    bool changed = false;
    for (std::size_t i = 1; i < end; ++i) {
      if (a[i - 1] > a[i]) {
        std::swap(a[i - 1], a[i]);
        changed = true;
      }
    }
    if (!changed) {
      return;
    }
  }
}

它适合教学、检测少量相邻逆序，或数据规模极小的场合；作为通用排序并不推荐。时间为最好 $O(n)$、平均和最坏 $O(n^2)$，空间 $O(1)$，稳定且原地。

选择排序：每轮固定一个最小值

不变量是 [0, i) 始终存放原数组中最小的 i 个元素并已排序。第 i 轮扫描后缀找到最小下标，再与 i 交换。无论输入如何，比较次数都是$n(n-1)/2$；但写入（交换）至多 $n-1$ 次，适合比较便宜而写入异常昂贵的介质。

#include <cstddef>
#include <utility>
#include <vector>

void selectionSort(std::vector<int>& a) {
  for (std::size_t i = 0; i < a.size(); ++i) {
    std::size_t best = i;
    for (std::size_t j = i + 1; j < a.size(); ++j) {
      if (a[j] < a[best]) {
        best = j;
      }
    }
    if (best != i) {
      std::swap(a[i], a[best]);
    }
  }
}

标准实现不稳定，最坏、平均、最好均为 $O(n^2)$，空间 $O(1)$。若业务需要稳定，可将最小元素右移并整体左移中间段，但写入次数会增加到 $O(n^2)$。

插入排序：维护一个有序前缀

处理到下标 i 时，不变量是 [0, i) 已排序且恰好是输入前缀的重排。保存a[i] 为 key，把所有比它大的元素向右移动一格，最后把 key 填入空位。移动而非反复交换，既更直接，也自然保持相等元素原有顺序。

#include <cstddef>
#include <vector>

void insertionSort(std::vector<int>& a) {
  for (std::size_t i = 1; i < a.size(); ++i) {
    const int key = a[i];
    std::size_t pos = i;
    while (pos > 0 && a[pos - 1] > key) {
      a[pos] = a[pos - 1];
      --pos;
    }
    a[pos] = key;
  }
}

它稳定、原地、在线，最好 $O(n)$、最坏 $O(n^2)$，并且准确地做了$O(n+I)$ 量级工作。几乎有序、每次只插入少量新元素，或递归排序切换到很小分段时，插入排序往往优于复杂算法。

希尔排序：让远距离逆序先移动

希尔排序把插入排序作用于若干间隔为 gap 的子序列。间隔逐步缩小到 1；前面的“粗排”会消掉长距离逆序，最后一次普通插入排序就更轻。它原地、实现简单，但不稳定：跨 gap 移动可能颠倒相等元素。

#include <cstddef>
#include <vector>

void shellSort(std::vector<int>& a) {
  for (std::size_t gap = a.size() / 2; gap > 0; gap /= 2) {
    for (std::size_t i = gap; i < a.size(); ++i) {
      const int key = a[i];
      std::size_t pos = i;
      while (pos >= gap && a[pos - gap] > key) {
        a[pos] = a[pos - gap];
        pos -= gap;
      }
      a[pos] = key;
    }
  }
}

上述折半增量的最坏上界可达 $O(n^2)$，实际表现通常较好，但没有像归并或堆那样强的统一保证。Sedgewick、Tokuda 等增量序列可改善理论与实践常数；若需求是可预测的最坏 $O(n\log n)$，不要把希尔排序当替代品。

归并排序：稳定性用线性辅助空间换来

归并排序是分治的典型实例：递归排序左右半区，再把两个有序区间合并。合并时若 a[i] <= a[j] 取左侧元素，左侧相等键必定先进入结果，因此算法稳定。递推为

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n).$$

合并不变量与完整模板

out 的已写前缀始终是两个输入已消费元素的稳定有序归并；两个指针之后的元素仍保持各自有序。某一侧耗尽后，另一侧剩余元素可整体追加。辅助数组只分配一次并贯穿递归，避免每层反复分配。

#include <cstddef>
#include <vector>

void mergeRange(std::vector<int>& a, std::vector<int>& buf,
                std::size_t left, std::size_t mid,
                std::size_t right) {
  std::size_t i = left;
  std::size_t j = mid;
  std::size_t out = left;
  while (i < mid && j < right) {
    if (a[i] <= a[j]) {
      buf[out++] = a[i++];
    } else {
      buf[out++] = a[j++];
    }
  }
  while (i < mid) {
    buf[out++] = a[i++];
  }
  while (j < right) {
    buf[out++] = a[j++];
  }
  for (std::size_t k = left; k < right; ++k) {
    a[k] = buf[k];
  }
}

void mergeSortRange(std::vector<int>& a, std::vector<int>& buf,
                    std::size_t left, std::size_t right) {
  if (right - left <= 1) {
    return;
  }
  const std::size_t mid = left + (right - left) / 2;
  mergeSortRange(a, buf, left, mid);
  mergeSortRange(a, buf, mid, right);
  mergeRange(a, buf, left, mid, right);
}

void mergeSort(std::vector<int>& a) {
  std::vector<int> buf(a.size());
  mergeSortRange(a, buf, 0, a.size());
}

归并排序在最好、平均、最坏情况下均为 $O(n\log n)$，辅助空间 $O(n)$，递归栈$O(\log n)$，稳定但通常不算原地。链表归并可通过改指针把额外空间降到$O(1)$；数组上的真正稳定原地归并很复杂，工程上通常不值得手写。

与逆序对的连接

若合并时 right[j] < left[i]，则 left[i..mid) 的所有元素都大于right[j]，可一次贡献 mid - i 个逆序对。这正是分治文章中的逆序对计数技巧：排序过程没有额外比较，却把跨区间逆序对在线统计出来。注意计数上限为$n(n-1)/2$，int 很容易溢出，答案应使用 std::int64_t 或更宽类型。

快速排序：随机枢轴与三路划分

快速排序的关键不是“递归”，而是一次线性划分将元素放入正确的相对区域。普通二路划分在大量相等键上会退化；荷兰国旗三路划分把区间拆成 < pivot、== pivot、> pivot，相等部分不再递归。

区间不变量

在处理半开区间 [left, right) 时维护：

• [left, less) 中元素严格小于 pivot；
• [less, scan) 中元素等于 pivot；
• [scan, greater) 尚未分类；
• [greater, right) 中元素严格大于 pivot。

读到小值，与 less 交换后同时前进 less、scan；读到等值只前进 scan；读到大值与 --greater 交换，不能前进 scan，因为换入元素尚未检查。循环结束后仅递归 < 与 > 两段。

#include <cstddef>
#include <random>
#include <utility>
#include <vector>

void quickSortRange(std::vector<int>& a, std::size_t left,
                    std::size_t right, std::mt19937& rng) {
  while (right - left > 1) {
    std::uniform_int_distribution<std::size_t> pick(
        left, right - 1);
    const int pivot = a[pick(rng)];
    std::size_t less = left;
    std::size_t scan = left;
    std::size_t greater = right;

    while (scan < greater) {
      if (a[scan] < pivot) {
        std::swap(a[less++], a[scan++]);
      } else if (a[scan] > pivot) {
        std::swap(a[scan], a[--greater]);
      } else {
        ++scan;
      }
    }

    if (less - left < right - greater) {
      quickSortRange(a, left, less, rng);
      left = greater;
    } else {
      quickSortRange(a, greater, right, rng);
      right = less;
    }
  }
}

void quickSort(std::vector<int>& a) {
  std::random_device seed;
  std::mt19937 rng(seed());
  quickSortRange(a, 0, a.size(), rng);
}

该模板总是递归较短一侧、循环处理较长一侧，因此显式递归深度为$O(\log n)$。随机枢轴使期望时间为 $O(n\log n)$，并降低针对固定取首元素、取尾元素的构造输入风险；它不消除最坏 $O(n^2)$，只使发生概率很低。若接口必须给出最坏 $O(n\log n)$ 保证，改用堆排序、归并排序，或直接用实现了introsort 的 std::sort。

快速排序原地（不计栈）且缓存友好，但不稳定。三路版本对少量不同键、大量重复键特别有效：全相等输入一次划分就结束，而二路版本可能生成极不平衡的递归树。

堆排序：用堆顶反复选出最大值

堆排序先把数组建成最大堆，再将堆顶交换到当前末端、缩小堆并下沉新堆顶。堆的完整定义、建堆与优先队列应用见堆；这里强调它在排序坐标系中的位置：建堆 $O(n)$，每次取最大和修复 $O(\log n)$，总时间在所有输入上都是$O(n\log n)$，额外空间 $O(1)$，但不稳定。

#include <algorithm>
#include <cstddef>
#include <vector>

void siftDown(std::vector<int>& a, std::size_t root,
              std::size_t size) {
  while (true) {
    const std::size_t left = root * 2 + 1;
    if (left >= size) {
      return;
    }
    const std::size_t right = left + 1;
    std::size_t child = left;
    if (right < size && a[right] > a[left]) {
      child = right;
    }
    if (a[root] >= a[child]) {
      return;
    }
    std::swap(a[root], a[child]);
    root = child;
  }
}

void heapSort(std::vector<int>& a) {
  for (std::size_t i = a.size() / 2; i > 0; --i) {
    siftDown(a, i - 1, a.size());
  }
  for (std::size_t end = a.size(); end > 1; --end) {
    std::swap(a[0], a[end - 1]);
    siftDown(a, 0, end - 1);
  }
}

它适用于内存紧、又不能承受快排最坏退化的场景。实际常数与缓存局部性通常不如快速排序；只需要不断取当前最小/最大而非最终完整数组时，更应直接使用优先队列。

非比较排序：把键的表示当作算法的一部分

计数排序：值域小才是真前提

计数排序统计每个整数值出现次数，随后按值写回。若键落在闭区间[minValue, maxValue]，计数数组长度为$R=maxValue-minValue+1$，时间和空间都是 $O(n+R)$。因此“线性”只在 $R$ 与$n$ 同阶时有意义；值域是 $10^9$ 而数据只有 100 个时，直接分配桶是灾难。

负数不能直接作下标。 必须令 offset = value - minValue，并用更宽的整数计算范围，避免 maxValue - minValue + 1 在 int 中先溢出。

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <vector>

void countingSort(std::vector<int>& a) {
  if (a.empty()) {
    return;
  }
  const auto [minIt, maxIt] =
      std::minmax_element(a.begin(), a.end());
  const std::int64_t low = *minIt;
  const std::int64_t high = *maxIt;
  const std::int64_t range = high - low + 1;
  if (range <= 0 || static_cast<std::uint64_t>(range) >
                        static_cast<std::uint64_t>(a.max_size())) {
    throw std::length_error("counting range is too large");
  }
  std::vector<std::size_t> count(
      static_cast<std::size_t>(range), 0);
  for (const int value : a) {
    ++count[static_cast<std::size_t>(
        static_cast<std::int64_t>(value) - low)];
  }
  std::size_t out = 0;
  for (std::size_t index = 0; index < count.size(); ++index) {
    const int value = static_cast<int>(
        low + static_cast<std::int64_t>(index));
    for (std::size_t times = count[index]; times > 0; --times) {
      a[out++] = value;
    }
  }
}

这个“写回”版本只排序整数值，谈不上保留记录的相对顺序；若要稳定地排序记录，需先对计数做前缀和，再从右向左把元素放入输出数组。那会使用 $O(n+R)$额外空间，但可作为基数排序的稳定子程序。

桶排序：均匀分布才有期望线性

桶排序把值域划为若干子区间，元素按映射散入桶，再分别排序并串接。对均匀分布的$[0,1)$ 浮点数，取 $n$ 个桶时，期望每桶常数个元素，期望时间可到 $O(n)$；若全部元素落进同一桶，退化为桶内排序的代价。桶边界、浮点精度、数据分布都是输入契约，而不是实现细节。

#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <vector>

void bucketSortUnit(std::vector<double>& a) {
  if (a.empty()) {
    return;
  }
  std::vector<std::vector<double>> buckets(a.size());
  for (const double value : a) {
    if (value < 0.0 || value >= 1.0) {
      throw std::invalid_argument("value must be in [0, 1)");
    }
    const std::size_t index = static_cast<std::size_t>(
        value * static_cast<double>(a.size()));
    buckets[index].push_back(value);
  }
  std::size_t out = 0;
  for (auto& bucket : buckets) {
    std::sort(bucket.begin(), bucket.end());
    for (const double value : bucket) {
      a[out++] = value;
    }
  }
}

这里桶内 std::sort 不稳定，因而整体也不保证稳定；若记录顺序重要，应改用稳定桶内排序并保证桶映射不会让相同键分裂到不同桶。

LSD 基数排序：每一位都必须稳定

LSD（least significant digit）从最低有效位开始，对每一位执行一次稳定分发。设基数为 $B$、最大键有 $d$ 位，时间为 $O(d(n+B))$，空间为 $O(n+B)$。低位已经形成的次序，只有在高位分发稳定时才会在同高位组内保留；任何一轮不稳定都会破坏此前所有工作。

下面模板排序无符号 32 位整数，采用 $B=256$，每轮处理一个字节，固定 4 轮。从原数组顺序读取、按累积起点写入输出缓冲，恰好保证同一桶内的稳定性。负整数不能直接套用：可以拆分负数与非负数，分别按绝对值排序再反向负数部分；或将有符号键通过翻转符号位映射到无符号字典序。

#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

void lsdRadixSort(std::vector<std::uint32_t>& a) {
  std::vector<std::uint32_t> out(a.size());
  for (std::size_t byte = 0; byte < 4; ++byte) {
    std::array<std::size_t, 256> count{};
    const std::size_t shift = byte * 8;
    for (const std::uint32_t value : a) {
      const std::size_t digit = static_cast<std::size_t>(
          (value >> shift) & 0xFFU);
      ++count[digit];
    }
    std::size_t start = 0;
    for (std::size_t digit = 0; digit < count.size(); ++digit) {
      const std::size_t frequency = count[digit];
      count[digit] = start;
      start += frequency;
    }
    for (const std::uint32_t value : a) {
      const std::size_t digit = static_cast<std::size_t>(
          (value >> shift) & 0xFFU);
      out[count[digit]++] = value;
    }
    a.swap(out);
  }
}

MSD 基数排序则从最高位分桶并递归处理每个桶，适合字符串或可变长度键；LSD 更适合固定宽度整数。基数大小不是越大越好：较大 $B$ 减少轮数，却增大计数数组、清零成本和缓存压力。

标准库：先描述语义，再选算法

除非题目要求手写，优先使用标准库。它们把多年工程优化、异常安全与边界处理封装在清晰语义中；但比较器契约仍由调用者负责。

#include <algorithm>
#include <cstddef>
#include <string>
#include <vector>

struct Record {
  int score;
  std::string id;
};

bool byScore(const Record& lhs, const Record& rhs) {
  return lhs.score < rhs.score;
}

void orderRecords(std::vector<Record>& records, std::size_t k) {
  std::sort(records.begin(), records.end(), byScore);
  std::stable_sort(records.begin(), records.end(), byScore);
  if (k < records.size()) {
    std::nth_element(records.begin(), records.begin() +
                     static_cast<std::ptrdiff_t>(k),
                     records.end(), byScore);
  }
}

• std::sort：不稳定，通常为 introsort：快排获得平均性能，递归过深改堆排序，小段用插入排序；比较次数最坏 $O(n\log n)$，额外空间通常为 $O(\log n)$。要完整排序且不需稳定性时默认选它。
• std::stable_sort：稳定，比较次数通常 $O(n\log n)$；可用足够缓冲时额外空间$O(n)$，标准也允许缓冲不足时以更多比较换空间。需要保持同键记录输入次序时用它。
• std::nth_element(first, first + k, last)：把第 $k$（从零开始）个元素放到最终排序位置，左侧没有元素大于它，右侧没有元素小于它；两侧未排序。平均/通常为线性复杂度，适合第 $K$ 小、中位数、TopK 分界。若还要左侧升序，继续排序[first, first + k)。

nth_element 后不能对整个区间二分，也不能假设前 $K$ 个元素已有序；它只给出分区性质。若要实时维护持续变化的 TopK，优先考虑大小为 $K$ 的堆，而非每次重排。

严格弱序：比较器最容易被忽略的前置条件

传给排序的 comp(a, b) 必须是严格弱序：comp(x, x) 为假；若 a < b 则不应有 b < a；传递性必须成立；等价关系也必须传递。不要写 lhs.score <= rhs.score，它让 comp(x, x) 为真，行为未定义；不要让比较器依赖会在排序期间改变的全局状态；浮点 NaN 也需要先定义业务排序规则。对于复合键，使用 std::tie 或分支比较，而不是相减：lhs.key - rhs.key < 0 会发生整数溢出。

#include <string>
#include <tuple>

struct Student {
  int grade;
  std::string name;
};

bool byGradeThenName(const Student& lhs, const Student& rhs) {
  return std::tie(lhs.grade, lhs.name) <
         std::tie(rhs.grade, rhs.name);
}

从实现到证明：不变量比“跑通样例”更可靠

排序代码很短，却很容易在边界上失真。n = 0、全部相等、严格降序、最大值与最小值并存，分别会暴露无符号下标下溢、分区停滞、递归不收缩和范围溢出。与其为每种输入补特判，不如先写出循环不变量，再检查每次迭代是否保持它、退出时是否足以推出后置条件。

什么是排序正确性

一个排序过程应同时满足两个条件：

1. 有序性：输出中任意相邻下标 i、i + 1 都满足!comp(a[i + 1], a[i])。对整数升序比较器，这就是 a[i] <= a[i + 1]。
2. 排列性：输出恰好包含输入的所有元素及其重数，没有丢、没有凭空产生、没有重复写入。对记录还应保持每条记录整体移动，而不只是移动排序键。

比较排序的正确性证明通常将这两个目标分开。有序性来自前缀、堆或分区不变量；排列性来自每一步只交换、移动或从两个输入段消费一个元素。归并排序的 buf覆盖 [left, right) 时，out 每前进一次恰好消费一个输入元素，因此排列性是逐位置建立的。快速排序只做交换，排列性则立即保持。

插入排序的归纳证明

插入排序的循环不变量是：处理 i 前，[0, i) 已有序，且它是原输入前 i个元素的排列。将 a[i] 存入 key 后，内层循环右移所有严格大于 key 的元素。右移并没有删掉元素；空出的 pos 是唯一可插入位置，且其左侧不大于key、右侧严格大于 key。写回 key 后，新前缀既有序又包含原来前缀加上这个 key 的全部元素。

注意“严格大于”正是稳定性的证明点。若内层条件误写成 a[pos - 1] >= key，新来的等键会越过旧等键，算法仍有序但不再稳定。这一差异在只排序整数时难以看见，却会在“按金额排序但保留入账先后”的记录上造成业务错误。

归并的边界设计：半开区间

本文模板统一采用 [left, right) 半开区间。它的长度总是 right - left，空区间自然写为 [x, x)，两个相邻区间 [left, mid) 与 [mid, right) 没有重叠也没有缺口。与闭区间版本相比，不需要在 mid + 1、right - left + 1 之间来回转换，尤其能减少递归基和尾部复制的 off-by-one 错误。

合并循环退出时至少一侧耗尽。若左侧耗尽，右侧余下元素已经不小于已输出前缀的最后元素；若右侧耗尽同理，因此直接复制剩余段不会破坏有序性。稳定性还要求在比较相等时取左侧：这让原先位于左半、也就是原序列中更靠前的记录先写出。

快排分区为何不会漏检元素

三路分区中最难的一行是处理 a[scan] > pivot 后不递增 scan。此时交换对象来自 --greater，它原来位于未分类区的末尾，可能小于、等于或大于枢轴；若立即跳过，便可能把一个小值误留在右侧。每轮循环至少缩小未分类区 [scan, greater)：小值和等值使 scan 增加，大值使 greater 减少，所以循环必然终止。

分区完成后，[left, less) 严格小于枢轴、[less, greater) 等于枢轴、[greater, right) 严格大于枢轴。递归分别把左右严格区间排序，就能拼成整体有序数组；等值段已无需处理。这也是三路版本面对重复值比二路版本更好的根本原因，而不只是“多了一个 if”。

复杂度不能脱离成本模型

比较、交换、移动并不是同一件事

渐近时间通常把一次比较、一次赋值都视为常数，但对象类型会让它们的成本相差几个数量级。排序 int 时，比较和交换都很轻；排序包含长字符串、文件句柄或大缓冲区的记录时，比较可能触发多字节扫描，移动也可能影响缓存与所有权。

• 选择排序固定进行 $\\Theta(n^2)$ 次比较，却只做 $O(n)$ 次交换。
• 冒泡排序比较数相近，但逆序输入会进行 $\\Theta(n^2)$ 次交换。
• 插入排序的移动数恰与逆序对数同阶，近乎有序时很少移动。
• 归并排序每层读写整个数组，连续访问对缓存和预取很友好，但必须承担额外缓冲。
• 堆排序理论最坏优秀，节点在数组中按树状跳跃，实践里往往比连续扫描的归并或快排有更差的缓存局部性。

因此“选择排序写得少”不能推出它适合 SSD，也不能推出它在所有写放大场景最佳。还要确认交换一个记录是否为常数成本、设备是否有擦写块、是否可排序间接索引。当记录很大时，常见工程方案是把记录放在原处，排序一组小型索引或指针；这改变了移动成本，却需要额外注意间接访问的缓存未命中。

比较下界的适用范围

$\\Omega(n\\log n)$ 下界有三个隐含前提：元素之间没有可用数值结构，算法只能问两元素的相对顺序，而且目标是区分所有可能排列。若键是 32 位无符号整数，读取一个字节就是获得八个二进制位的信息，LSD 基数排序可以不做两两比较。若元素只来自[0, 100]，计数数组把“这个值出现几次”直接编码，排序也不再需要识别 $n!$ 种相对比较路径。

反过来，不能看到整数就机械选基数排序。对只有几百个元素、键已在 CPU 缓存中的普通数组，初始化 256 个计数桶、分配输出数组、进行多轮全量读写，可能比std::sort 更慢。复杂度中的 $d$、$B$、内存带宽和分配成本都是真实成本。

稳定性的传递与多关键字排序

假设记录先按 id 升序稳定排序，再按 score 降序稳定排序。第二次排序只改变不同分数的组间位置；分数相同的记录保留第一次排序建立的 id 次序，最终就是“score 降序、id 升序”的字典序。这种写法比手写多分支比较器直观，但前提是两次都稳定。

更常用也更省一次排序的方法是复合比较器。稳定排序并不能修复一个不完整比较器：若业务需要在同分时按 id，则 std::sort 配合完整的(score, id) 比较器已经给出确定顺序；只有“同键保持输入语义”本身有价值时，才必须选择稳定排序。

稳定性还具有组合规律：稳定分区与稳定的递归子排序可构成稳定排序；任何一步让相等元素交叉的交换都会破坏全局稳定性。归并排序使用 <= 选左，LSD 基数排序保持桶内输入顺序，都是同一个规律的不同表现。

归并排序的工程变体

自底向上：避免递归栈

递归归并自顶向下，结构贴合分治证明；自底向上则从长度为 1 的段开始，依次合并长度为 1、2、4、8 的相邻段。两者都是 $O(n\\log n)$、稳定、需 $O(n)$ 缓冲，但迭代版没有递归调用，更适合迭代器范围、外部排序的多路归并，或希望显式控制工作批次的场景。

每一轮宽度 width 开始前，数组由若干长度至多为 width 的有序段组成；合并相邻段后，长度至多为 2 * width 的段有序。末尾不足一整段时，以剩余长度截断右边界。边界计算先做减法再做加法，避免在极大 size_t 上先发生溢出。

#include <algorithm>
#include <cstddef>
#include <vector>

void mergeRuns(std::vector<int>& a, std::vector<int>& buf,
               std::size_t left, std::size_t mid,
               std::size_t right) {
  std::size_t i = left;
  std::size_t j = mid;
  std::size_t out = left;
  while (i < mid && j < right) {
    if (a[i] <= a[j]) {
      buf[out++] = a[i++];
    } else {
      buf[out++] = a[j++];
    }
  }
  while (i < mid) {
    buf[out++] = a[i++];
  }
  while (j < right) {
    buf[out++] = a[j++];
  }
  for (std::size_t k = left; k < right; ++k) {
    a[k] = buf[k];
  }
}

void bottomUpMergeSort(std::vector<int>& a) {
  std::vector<int> buf(a.size());
  for (std::size_t width = 1; width < a.size();) {
    const std::size_t remain = a.size() - width;
    const std::size_t step = width > remain ? a.size() : width * 2;
    for (std::size_t left = 0; left < a.size();) {
      const std::size_t leftSize = a.size() - left;
      const std::size_t mid = left + std::min(width, leftSize);
      const std::size_t right =
          mid + std::min(width, a.size() - mid);
      mergeRuns(a, buf, left, mid, right);
      if (a.size() - left <= step) {
        break;
      }
      left += step;
    }
    if (width > a.size() / 2) {
      break;
    }
    width *= 2;
  }
}

这里 step 至多为 a.size()，内层循环在加法前检查剩余长度，因此不会让步长或left 的推进先溢出。即便在题目规模远小于地址空间上限时，这种写法也让区间契约与半开区间风格保持一致。

自然归并与近乎有序输入

真实数据经常包含已排序的 run，例如按时间追加的日志、按分区读取的表。自然归并先扫描并识别天然单调段，只在段之间合并；若输入本来只有一个 run，扫描后就结束。这也是许多稳定排序实现能对近乎有序输入表现出适应性的原因。

要识别降序 run 时需谨慎：把严格递减段反转不会破坏相等键顺序；把“非递增”段整体反转则会反转相等元素，损失稳定性。稳定排序的优化必须把等键情况单独纳入不变量，不能只关注数值是否有序。

外部排序：内存不足时仍以归并为中心

当数据不能同时放入内存，流程通常是：读入可容纳的一块，内存中排序并写成有序run；再用优先队列做 $k$ 路归并，每次输出当前最小记录并从同一 run 读取下一条。I/O 次数而非 CPU 比较数成为瓶颈，块大小、缓冲与归并路数决定性能。

外部排序解释了归并排序在数据库和文件处理中的长寿：它只要求每个输入 run 有序，合并可以流式进行。快速排序的原地分区在内存数组上极快，却不自然适配顺序磁盘流；算法选型总要匹配数据所在的介质。

快速排序的性能边界

为什么固定枢轴会被构造输入击穿

若每轮总选第一个元素作为枢轴，而输入已经升序，划分得到大小为 0 和 $n-1$ 的两个问题：

$$T(n)=T(n-1)+\\Theta(n)=\\Theta(n^2).$$

递归树高度变成 $n$，不仅慢，还会使递归栈爆掉。取中间下标也不是万能：攻击者可按已知策略构造“中位下标元素总是极端”的排列。随机枢轴避免了输入与固定策略的确定耦合，三数取中则是常见启发式；两者都不是数学意义上的最坏保证。

标准库常用 introsort 的思路很实用：开始按快排运行，观察递归深度；一旦深度超过与 $\\log n$ 成比例的阈值，就切换至堆排序。这样通常输入保留快排的局部性，恶意输入也不突破 $O(n\\log n)$。不要依赖某个库恰好使用某种内部算法；调用者可依赖的是标准承诺的语义与复杂度界，而不是私有实现细节。

分区方案的选择

Hoare 分区交换较少，Lomuto 分区更直观但遇到重复元素往往不均衡，三路荷兰国旗分区专门压缩等值段。没有单一方案绝对最好：

• 键几乎互异、实现追求简洁时，二路分区已足够；
• 键域小、重复比例高时，三路分区显著减少递归；
• 记录交换很贵时，应衡量分区交换数与比较器成本；
• 需要稳定性时，不应尝试给原地快排“补一个稳定特判”，而应直接选归并或std::stable_sort。

使用三路划分时，枢轴值必须先复制到局部变量。若只保存指向数组中枢轴位置的引用，后续交换可能移动该位置的元素，比较目标随过程改变，分区不变量立即失效。对于大对象可保存独立的键或使用索引间接排序，但不能让 pivot 的比较语义漂移。

尾递归消除与栈上界

即使枢轴随机，单次运行仍有可能形成长链。模板递归较短区间并用 while 继续较长区间，保证每进入一层递归，正在递归的区间长度至少减半，所以栈深最多$O(\\log n)$。这与运行时间的期望性质不同：栈上界是由“先处理小段”的控制流确定的，不需要假定枢轴平衡。

TopK、全排序与部分有序的边界

“取最大的 K 个”至少有三种不同语义，不能只按函数名选算法：

1. 只要第 $K$ 小元素的值或第 $K$ 个位置：nth_element，平均 $O(n)$。
2. 要一组任意顺序的前 $K$ 个：nth_element 后取前缀，仍不保证前缀有序。
3. 要前 $K$ 个且按序输出：nth_element 后排序前缀，约为$O(n + K\\log K)$；或维护 $K$ 大小的堆，约为 $O(n\\log K)$。

当 $K$ 远小于 $n$、数据以流形式到达时，大小为 $K$ 的最小堆（求最大 K 个）不需要保存全部历史元素，空间 $O(K)$；当所有数据已在内存且只做一次选择，nth_element 通常更合适。完整 std::sort 为 $O(n\\log n)$，只有当你确实需要全序、后续要做二分或要输出完整排行榜时才支付这笔工作。

第 $K$ 个元素的“第”也要在接口中写清楚：人类往往从 1 开始计数，迭代器偏移从0 开始。若 k 是一基排名，目标迭代器为 first + (k - 1)，并必须先验证1 <= k && k <= n。空数组与越界不是 nth_element 自动处理的业务规则。

数据分布与键表示：线性排序的真实门槛

计数排序为何经常“理论正确、工程错误”

设 20 个温度读数位于 [-50, 50]，值域 $R=101$，计数排序只需一个很小的数组，几乎是最直接的办法。换成 20 个订单号，数值可能覆盖整个 32 位范围，即使它们恰好是整数，$R$ 也接近 $2^{32}$；按值域开数组既无法分配，也没有必要。计数排序的决策式不是“键是 int 吗”，而是：

$$R = \max(key)-\min(key)+1$$

是否能接受，且 $R$ 是否相对 $n$ 足够小。

对于记录排序，稳定计数的过程分三步：先统计每个偏移的频数；将频数变换为每个值在输出数组的起始位置；再按原输入从左到右扫描，写入 out[next[key]++]。从左到右以及“每桶位置递增”共同保证相等键保序。以下模板展示记录稳定排序，并显式把偏移运算提升到 64 位。

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>

struct Event {
  int priority;
  std::string id;
};

void stableCountingSort(std::vector<Event>& events) {
  if (events.empty()) {
    return;
  }
  int low = events.front().priority;
  int high = events.front().priority;
  for (const Event& event : events) {
    low = std::min(low, event.priority);
    high = std::max(high, event.priority);
  }
  const std::int64_t range =
      static_cast<std::int64_t>(high) - low + 1;
  if (range <= 0 || static_cast<std::uint64_t>(range) >
                        static_cast<std::uint64_t>(
                            events.max_size())) {
    throw std::length_error("counting range is too large");
  }
  std::vector<std::size_t> next(
      static_cast<std::size_t>(range), 0);
  for (const Event& event : events) {
    const auto index = static_cast<std::size_t>(
        static_cast<std::int64_t>(event.priority) - low);
    ++next[index];
  }
  std::size_t start = 0;
  for (std::size_t& count : next) {
    const std::size_t frequency = count;
    count = start;
    start += frequency;
  }
  std::vector<Event> out(events.size());
  for (const Event& event : events) {
    const auto index = static_cast<std::size_t>(
        static_cast<std::int64_t>(event.priority) - low);
    out[next[index]++] = event;
  }
  events = std::move(out);
}

events = std::move(out) 移交输出数组的存储；稳定性并不依赖这一步，而已在扫描输入时建立。若改为从右向左填充，也可以稳定，但必须配合“每桶末位置”而非上述起始位置；把两种写法混搭是计数排序最常见的反序 bug。

有符号整数的 LSD 基数排序

无符号整数的数值序与按高位到低位的位字典序一致。有符号二进制补码却把负数的最高位设为 1：直接将 int32_t 强转为 uint32_t 排序，会把所有负数排在正数后。最简洁的变换是翻转符号位：

key(x)=\\operatorname{uint32\\_t}(x)\\mathbin{\\mathtt{\\char`\\^}} 0x80000000.

该变换把 INT32_MIN 映射到 0、把 0 映射到 $2^{31}$，保持有符号升序对应的无符号升序。排序时可以携带原值与映射键，或在分发时对每个字节读取变换后的键。下面代码只使用固定宽度类型，避免 int 位宽和右移负数的实现细节。

#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

std::uint32_t radixKey(std::int32_t value) {
  return static_cast<std::uint32_t>(value) ^ 0x80000000U;
}

void signedLsdRadixSort(std::vector<std::int32_t>& a) {
  std::vector<std::int32_t> out(a.size());
  for (std::size_t byte = 0; byte < 4; ++byte) {
    std::array<std::size_t, 256> count{};
    const std::size_t shift = byte * 8;
    for (const std::int32_t value : a) {
      const auto digit = static_cast<std::size_t>(
          (radixKey(value) >> shift) & 0xFFU);
      ++count[digit];
    }
    std::size_t start = 0;
    for (std::size_t& countAtDigit : count) {
      const std::size_t frequency = countAtDigit;
      countAtDigit = start;
      start += frequency;
    }
    for (const std::int32_t value : a) {
      const auto digit = static_cast<std::size_t>(
          (radixKey(value) >> shift) & 0xFFU);
      out[count[digit]++] = value;
    }
    a.swap(out);
  }
}

这个技巧也说明为何“负数偏移”有两层含义：计数排序以最小值作为数值偏移，基数排序则可用翻转符号位完成编码偏移。两者都不是给负数加一个任意常量；变换必须一一对应且保持目标顺序。

桶排序的映射需要精确定义

将 value * bucketCount 截断为下标，只在输入严格属于 [0, 1) 时安全。若允许1.0，结果下标恰等于 bucketCount 而越界；若允许负数或 NaN，转换为无符号下标更没有业务意义。实际接口应明确输入域，必要时先做验证或归一化。

“均匀分布”也不是一个魔法注释。桶数为 $m$、元素数为 $n$ 时，期望桶载荷为$n/m$；若桶内使用插入排序，均匀假设下的总工作近似线性。分布高度偏斜时，某个桶可能容纳 $\\Theta(n)$ 个元素，算法就退化。已知分位点、业务分段或哈希质量才能支持选择桶边界；不知道分布时，比较排序更稳妥。

字符串、浮点数与复合键

字符串可视为变长位串，但字典序需要处理结束符："a" 必须位于 "aa" 之前。MSD 基数排序适合按首字符分桶后递归，且需要把字符串结束标记视作小于任何真实字符的特殊码。LSD 更适合定长编码（邮编、固定长度 ID）；对变长 UTF-8 文本，直接按字节 LSD 往往不等价于按用户可见字符或语言规则排序。

浮点数包含 -0.0、正负无穷与 NaN。普通 < 对 NaN 既不小于也不大于任何值，会让“等价类”的业务语义含混。若确需排序，应先制定策略，例如把 NaN 全部放在末尾，再对非 NaN 使用数值比较；不能把未定义的域规则留给严格弱序比较器猜测。复合键同理：先写清楚每一级方向、缺失值位置和相等定义，再选择稳定排序或复合比较器。

标准库接口的可依赖语义

std::sort：完整但不稳定的排列

std::sort(first, last, comp) 将 [first, last) 重排为按 comp 有序的排列；具有等价键的元素相对顺序未指定。现代标准要求比较/投影应用次数具有$O(N\\log N)$ 上界，随机访问迭代器是它的接口门槛。标准不承诺某个具体的introsort 实现、枢轴策略或额外内存字节数；“快排加堆排兜底”是解释常见实现的好模型，不应把它写成跨平台语义依赖。

调用前要确认区间合法，且比较器对整个区间稳定地满足严格弱序。排序期间修改参与比较的键、让比较器读取不断变化的时钟、或比较两个对象时返回随机结果，都会破坏算法的前提；库没有义务从这种契约违例中恢复。

std::stable_sort：相等键的输入顺序是输出的一部分

std::stable_sort 的有序性与 std::sort 相同，额外承诺等价元素保持原相对顺序。若能取得足够临时内存，比较次数为 $O(N\\log N)$；内存受限时，标准允许使用 $O(N\\log^2N)$ 次比较的原地式策略。故“稳定排序总是同样快、只是多开数组”并不准确：稳定性有可见的内存与最坏比较成本边界。

排序记录前，可以先问一个更具体的问题：同键记录的输入顺序是否有语义？日志事件的接收顺序、同分选手的报名顺序、同金额订单的创建顺序，通常有；从数据库无序读取的无意义偶然顺序，通常没有。只有前者值得为稳定性支付代价。

std::nth_element：选择而非排序

调用 std::nth_element(first, nth, last, comp) 后，nth 指向若完整排序时会出现在该位置的元素；对任意左侧元素 x 和右侧元素 y，有!comp(*nth, x) 与 !comp(y, *nth) 的分区含义。左右侧内部可以任意排列，相等键如何分布到两侧也不保证稳定。

其平均比较次数为线性，交换次数也具有线性量级的典型实现成本；标准的复杂度表述还允许在特定实现中有更高的交换上界。若你需要严格最坏线性选择，需要专门的median-of-medians 实现，常数通常不值得为普通任务支付。把 nth 设为 last是越界；要第 k 个零基元素，必须满足 k < N。

何时直接使用 partial_sort

若希望前 $K$ 个元素本身有序、而不关心剩余元素，可使用std::partial_sort(first, first + k, last, comp)。它通常以堆维护大小为 $K$的候选集，比较复杂度约为 $O(N\\log K)$，前缀有序、后缀无序。它填补了nth_element（前缀无序）与全排序（做了过多工作）之间的语义空档。

#include <algorithm>
#include <cstddef>
#include <vector>

std::vector<int> smallestKSorted(std::vector<int> values,
                                 std::size_t k) {
  if (k > values.size()) {
    k = values.size();
  }
  std::partial_sort(values.begin(), values.begin() +
                    static_cast<std::ptrdiff_t>(k), values.end());
  values.resize(k);
  return values;
}

这个函数返回前 $K$ 个最小值并升序排列。k = 0 合法，partial_sort(first,first, last) 不会要求访问元素；若业务上把 K=0 视为错误，应由调用层而非排序算法层表达该约束。

选型：先把约束写出来

约束	推荐	理由与注意点
通用数组、完整排序	std::sort	最坏 $O(n\log n)$，常数和缓存表现通常最好
需要稳定且内存允许	std::stable_sort 或归并	保留同键记录顺序，通常需要 $O(n)$ 缓冲
近乎有序、小数组	插入排序	$O(n+I)$，移动少，适合作为叶子算法
写入次数极少	选择排序	至多 $n-1$ 次交换，但比较仍为 $O(n^2)$
内存极紧、需最坏保证	堆排序	$O(n\log n)$、$O(1)$ 辅助空间、不稳定
重复键极多	三路快速排序	等值区不递归，期望 $O(n\log n)$
键是小值域整数	计数排序	$O(n+R)$；先确认值域 $R$ 不会爆内存
均匀的区间实数	桶排序	分布假设成立时才有期望线性
固定宽度非负整数	LSD 基数排序	$O(d(n+B))$；每轮稳定分发不可省略
只需第 $K$ 小或分界	std::nth_element	不完整排序，平均线性；两侧无序
排序后大量查询	排序 + 二分	排序建立单调性，查询 $O(\log n)$

“按规模”不应只看 $n$：记录体积、比较器成本、CPU 缓存和分布也会改变阈值。一个昂贵的字符串比较器会让减少比较次数更重要；一个巨大对象数组可能更适合排序索引，再按索引访问对象。实践中应先选符合语义和复杂度保证的算法，再用真实负载测量。

复杂度对照

算法	最好	平均	最坏	额外空间	稳定	原地	关键前提
冒泡	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	提前退出才有最好线性
选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否	是	写入比比较昂贵
插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	近乎有序或小规模
希尔	依增量	依增量	常见为 $O(n^2)$	$O(1)$	否	是	增量序列决定表现
归并	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	是	否	可接受辅助数组
三路快排	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	否	是	随机枢轴，重复键多更佳
堆	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	否	是	需确定最坏上界
计数	$O(n+R)$	$O(n+R)$	$O(n+R)$	$O(n+R)$	可	否	整数、小值域
桶	$O(n)$	$O(n)$	$O(n^2)$	$O(n)$	取决于桶内	否	分布近似均匀
LSD 基数	$O(d(n+B))$	同左	同左	$O(n+B)$	是	否	固定长度整数/位串

常见陷阱清单

1. 把随机枢轴当作最坏保证。 随机化只把坏划分变成低概率事件；对抗性环境或严格 SLA 下，应选堆排序、归并排序或 introsort。
2. 中点、范围与逆序对计数溢出。 用 left + (right - left) / 2，范围计算先提升到 int64_t，逆序对答案不要放进 int。
3. 负数直接作为计数下标。 以最小值为偏移，并警惕 max - min + 1 本身的溢出和不合理内存申请。
4. 基数排序某一轮不稳定。 LSD 的高位分发必须保留低位的相对次序；从输入顺序读取并按前缀起点输出，是最直观的稳定写法。
5. 把 <= 放进排序比较器。 比较器必须满足严格弱序；相等元素应让两个方向都返回假。不要用相减比较整数键。
6. 把 nth_element 当作完整排序。 它只保证目标元素位置与两侧分区，不保证两侧内部次序。
7. 忽略稳定性的业务含义。 “按金额排序后仍保持提交先后”是稳定性需求，不是视觉细节；先判断它，再决定能否使用堆或快排。
8. 只看渐近式，不看输入契约。 计数排序的 $R$、桶排序的分布、基数排序的键宽度，都是复杂度式中不可省略的变量。

小结

排序的核心不是记住十几段代码，而是把问题放回模型：纯比较排序受$\Omega(n\log n)$ 下界约束；稳定性、内存和最坏保证决定归并、堆、快排的取舍；整数表示与分布信息才让计数、桶、基数排序跨过比较下界。通用场景先用std::sort，需要稳定用 std::stable_sort，只要第 $K$ 个用std::nth_element。当排序是后续二分查找的前处理时，真正获得的是可证明的单调性，而不仅是一组“看起来整齐”的数字。