排序算法

1. 概览与复杂度

排序是将序列按指定顺序重新排列的问题。它是计算机科学中研究最深入的问题之一——不是因为排序本身是最终目标，而是因为有序序列可以解锁 O(log n) 的二分查找、简化去重、实现高效合并，并构成数十种其他算法的预处理步骤。

基于比较的下界

任何通过比较元素来排序的算法在最坏情况下至少需要 Ω(n log n) 次比较。证明基于决策树论证：n 个元素共有 n! 种排列方式，因此对所有输入都正确的二叉决策树至少有 n! 个叶子节点，树高 ≥ log₂(n!) ≈ n log n。这意味着归并排序、快速排序和堆排序在基于比较的排序中都是渐进最优的。

非比较排序

计数排序、基数排序和桶排序通过利用键的结构（有界整数或均匀浮点数）而非比较来绕过 Ω(n log n) 下界。它们的运行时间为 O(n + k) 或 O(nk)，但需要额外空间并对输入有约束。

稳定与不稳定

稳定排序是指相等元素保持其原始相对顺序的排序。当先按主关键字排序、再按次关键字排序时，稳定性至关重要（例如先按成绩排序，再按姓名排序）。稳定排序：冒泡、插入、归并、计数、基数。不稳定排序：选择、标准快排、堆排序。

原地与非原地

原地排序仅使用 O(1) 辅助空间（不计调用栈）。原地：冒泡、选择、插入、堆、快速排序。非原地：归并排序 O(n)、计数 O(k)、基数 O(n+k)、桶排序 O(n+k)。

复杂度参考

2. 冒泡排序

冒泡排序多次遍历数组，比较相邻元素并在顺序错误时交换它们。每次遍历后，最大的未排序元素会「冒泡」到末尾的正确位置。它是最直观的排序算法，但实际效率最低。

核心思想

第 i 次遍历后，最后 i 个元素已在最终位置。每次遍历至少将一个元素放到正确位置，因此最多需要 n−1 次遍历。加入提前退出标志（若一次遍历无交换则停止），可在 O(n) 时间内检测已排序输入。

执行步骤

1. 从索引 0 开始。比较 arr[0] 和 arr[1]——若 arr[0] > arr[1]，则交换。
2. 移至索引 1。比较 arr[1] 和 arr[2]——若需要则交换。继续到索引 n−2。
3. 第一次遍历后，arr[n−1] 存放最大元素。
4. 对剩余 n−1 个元素重复。每次遍历将未排序区域缩小一位。
5. 若一次完整遍历没有发生任何交换，说明数组已排序——提前退出。

C++ 参考实现

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // already sorted
    }
}

复杂度

适用与不适用场景

• 教学目的——最容易解释和可视化的排序算法。
• 近乎有序的数据——加入提前退出后，当 k 个元素错位时，只需 k 次遍历，可超越 O(n log n) 排序的常数。
• 对于 n 超过几百的情况应避免使用——O(n²) 平均复杂度使其不实用。

3. 选择排序

选择排序将数组分为已排序前缀和未排序后缀。每次遍历在未排序后缀中找到最小元素，将其移到已排序前缀的末尾。它以始终执行 O(n²) 次比较（即使对已排序输入也如此）为代价，将写操作（交换）最小化。

核心思想

每次遍历选择剩余最小元素，通过恰好一次交换将其放到最终位置。k 次遍历后，前 k 个位置已正确填充。与冒泡排序不同，无论输入顺序如何，比较次数始终恰好为 n(n−1)/2——没有提前退出优化。

执行步骤

1. 设 min_idx = 0。扫描整个数组找到最小元素。
2. 将 arr[0] 与 arr[min_idx] 交换。现在 arr[0] 在最终位置。
3. 设 min_idx = 1。扫描 arr[1..n−1] 找最小值。
4. 将 arr[1] 与 arr[min_idx] 交换。现在 arr[0..1] 已排序。
5. 重复直到整个数组排序完毕（共 n−1 次遍历）。

C++ 参考实现

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        if (minIdx != i) swap(arr[i], arr[minIdx]);
    }
}

复杂度

适用与不适用场景

• 写操作非常昂贵时（如闪存）：总交换次数仅 O(n) 而非 O(n²)。
• 对已排序或近乎有序输入不关心性能时——没有提前退出。
• 需要稳定排序时应避免——改用插入排序。

4. 插入排序

插入排序逐个元素地构建有序前缀。它取下一个未排序元素并向左移动，直到找到正确位置——就像将一张牌插入已排好的手牌中。最坏情况为 O(n²)，但在近乎有序的数据上运行 O(n)，在实践中用作归并排序和快速排序小子数组的基础情况。

核心思想

在第 i 步，arr[0..i−1] 已排序。我们通过向后比较并将更大元素向右移一位来将 arr[i] 「插入」已排序前缀，直到找到 arr[i] 的位置。每个元素每次遍历最多移动一次，因此当元素接近最终位置时效率很高。

执行步骤

1. 从 i = 1 开始。保存 key = arr[1]。
2. 将 key 与 arr[0] 比较。若 arr[0] > key，将 arr[0] 右移到 arr[1]。
3. 将 key 插入现在空出的位置。arr[0..1] 现已排序。
4. 对 i = 2：保存 key = arr[2]。若 arr[1] > key 则右移，若需要再移 arr[0]。
5. 对所有元素重复。i 步后，arr[0..i] 已排序。

C++ 参考实现

void insertionSort(vector<int>& arr) {
    for (int i = 1; i < (int)arr.size(); i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

复杂度

适用与不适用场景

• 小数组（n < 16）：由于常数极小且无递归开销，比 O(n log n) 排序更快。用作 TimSort 和许多快速排序实现的基础情况。
• 近乎有序的数据：若最多 k 个元素错位，运行时间为 O(nk)。
• 在线排序：可在 O(n) 时间内将新元素合并到已排序序列中。
• 大 n 任意输入时应避免。

5. 归并排序

归并排序是一种分治算法，将数组递归地对半分割，排序每半部分，然后在 O(n) 时间内将两个有序半部分合并。在所有情况下都保证 O(n log n)，且稳定，是需要可预测性能或稳定性时的首选排序。

核心思想

分解：在中点分割（O(1)）。解决：递归排序两半。合并：通过反复取前端较小元素，在 O(n) 时间内将两个有序数组合并为一个。递推关系为 T(n) = 2T(n/2) + O(n)，由主定理（情形 2）解为 O(n log n)。

执行步骤

1. 基础情况：若数组有 0 或 1 个元素，已排序——返回。
2. 找 mid = len(arr) // 2。分为 left = arr[:mid] 和 right = arr[mid:]。
3. 递归排序 left 和 right。
4. 合并：用两个指针 i、j 从 left 和 right 的前端开始。反复将较小元素追加到结果数组。
5. 将未耗尽的那半剩余元素追加。
6. 返回合并后的结果。

C++ 参考实现

void merge(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> tmp(arr.begin()+lo, arr.begin()+hi+1);
    int i = 0, j = mid-lo+1, k = lo;
    while (i <= mid-lo && j < (int)tmp.size())
        arr[k++] = (tmp[i] <= tmp[j]) ? tmp[i++] : tmp[j++]; // <= preserves stability
    while (i <= mid-lo) arr[k++] = tmp[i++];
    while (j < (int)tmp.size()) arr[k++] = tmp[j++];
}

void mergeSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid+1, hi);
    merge(arr, lo, mid, hi);
}

重要变体

复杂度

适用与不适用场景

• 必须保证最坏情况 O(n log n) 时（例如问题约束不允许随机枢轴）。
• 需要稳定排序时。
• 排序链表——分割和合并自然地不需要随机访问。
• 外部排序（数据不适合内存）。
• 禁止使用 O(n) 额外空间时应避免——改用堆排序。

6. 快速排序

快速排序选择一个枢轴元素，将数组分区使所有 ≤ 枢轴的元素在左侧，所有 > 枢轴的在右侧，然后递归排序两侧。它原地、缓存友好，是实践中最快的比较排序——尽管在没有良好枢轴策略时最坏情况为 O(n²)。

核心思想

分区后，枢轴处于其最终有序位置。递归排序左右分区。递推关系为 T(n) = T(k) + T(n−k−1) + O(n)，k 为枢轴排名。枢轴接近中位数时 k ≈ n/2，T(n) = O(n log n)；枢轴始终是最小/最大值时 k = 0，T(n) = O(n²)。

分区步骤（Lomuto 方案）

1. 选择 pivot = arr[hi]（最后一个元素）。设 i = lo − 1。
2. 对 j 从 lo 到 hi−1：若 arr[j] <= pivot，则 i 加一并交换 arr[i] 与 arr[j]。
3. 循环后，交换 arr[i+1] 与 arr[hi]。现在 arr[i+1] 是最终位置的枢轴。
4. 返回枢轴索引 i+1。
5. 递归：quickSort(arr, lo, pivot_idx − 1) 和 quickSort(arr, pivot_idx + 1, hi)。

C++ 参考实现

int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    swap(arr[i+1], arr[hi]);
    return i + 1;
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }
}

枢轴选择策略

三路分区（荷兰国旗问题）

当数组包含大量重复元素时，标准快速排序仍将重复元素分成两半并递归处理。三路分区（Dijkstra）保持三个区域：< 枢轴、== 枢轴、> 枢轴。相等元素不再被递归——当所有元素相等时，性能从 O(n log n) 提升到 O(n)。荷兰国旗问题（LeetCode 75）必备。

快速选择——第 K 大

不完全排序地找第 k 大元素：分区一次，然后只递归到包含排名 k 的那侧。期望 O(n) 时间。这是 LeetCode 215（数组中的第 K 个最大元素）背后的算法。

复杂度

适用与不适用场景

• 平均性能比最坏情况保证更重要时的通用排序。由于缓存局部性，实践中比归并排序快 2−3×。
• 没有额外内存时（原地）。
• O(n) 期望的第 k 顺序统计量快速选择。
• 不可接受最坏 O(n²) 时应避免——改用归并排序或堆排序。
• 需要稳定排序时应避免。

7. 堆排序

堆排序使用最大堆进行原地排序。阶段 1 在 O(n) 时间内从数组构建最大堆。阶段 2 反复提取最大值（通过将根与最后元素交换，堆大小减 1，对新根进行下沉）直到数组排序完毕。它在 O(1) 额外空间内实现 O(n log n) 最坏情况。

核心思想

最大堆具有每个节点 ≥ 其子节点的性质。根节点保存最大值。将最大值放到末尾（其有序位置），在剩余 n−1 个元素上恢复堆性质，从右向左排序。堆化（下沉）耗时 O(log n)，调用 n−1 次，得到 O(n log n)。从下往上堆化构建初始堆耗时 O(n)。

执行步骤

1. 构建最大堆：从索引 n//2−1 向下到 0，对每个非叶节点调用 heapify。
2. 将 arr[0]（最大值）与 arr[n−1] 交换。最后一个元素现在处于最终有序位置。
3. 将堆大小减为 n−1。调用 heapify(arr, n−1, 0) 恢复堆性质。
4. 将 arr[0] 与 arr[n−2] 交换。减小大小。再次堆化。
5. 重复直到堆大小为 1。数组已排序。

C++ 参考实现

void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

复杂度

适用与不适用场景

• 需要 O(n log n) 最坏情况 AND O(1) 额外空间时（唯一同时具备两个性质的排序）。
• 嵌入式/内存受限系统，无法承受 O(n) 额外空间。
• 作为 IntroSort 的回退（C++ std::sort 使用）：从快速排序开始，若递归深度超过 2 log n 则回退到堆排序，确保 O(n log n) 最坏情况。
• 缓存性能重要时应避免——快速排序在实践中快 2−5×。

8. 计数排序

计数排序是用于已知范围 [0, k] 内非负整数的非比较排序。它统计每个值出现的次数，然后用前缀和计算每个值在输出数组中的位置。运行时间为 O(n + k)，稳定，但需要 O(k) 额外空间，且只适用于整数键。

核心思想

若知道值 v 出现了 count[v] 次，且所有 < v 的值共占据 prefix[v] 个位置，则 v 应占据输出中从 prefix[v−1] 到 prefix[v−1] + count[v] − 1 的位置。通过反向遍历输入并递减计数，我们稳定地放置元素（v 的最后一次出现放到为 v 分配的最后一个槽位）。

执行步骤

1. 分配 count[0..k] = 0。对 arr 中每个 x：count[x]++。
2. 计算前缀和：对 i 从 1 到 k：count[i] += count[i−1]。现在 count[v] = ≤ v 的元素数量。
3. 构建输出数组：反向遍历 arr。对每个 x：count[x]−−；output[count[x]] = x。
4. 将 output 复制回 arr。
5. 反向遍历是保证排序稳定的关键——最后看到的重复元素放到最后一个可用槽位。

C++ 参考实现

void countingSort(vector<int>& arr, int k) {
    vector<int> cnt(k + 1, 0);
    for (int x : arr) cnt[x]++;
    for (int i = 1; i <= k; i++) cnt[i] += cnt[i-1];
    vector<int> out(arr.size());
    for (int i = arr.size()-1; i >= 0; i--)
        out[--cnt[arr[i]]] = arr[i];
    arr = out;
}

复杂度

适用与不适用场景

• 小有界范围内的整数：排序年龄（0–120）、考试成绩（0–100）或字符频率。
• 作为基数排序的子程序。
• k 相对于 n 很大时应避免（如对 100 个数在 0–10⁹ 范围内排序——改用比较排序）。
• 非整数或复合键时应避免。

9. 基数排序

基数排序从最低有效位（LSD）到最高有效位（MSD）逐位排序整数，每个数字位置使用稳定排序（通常是计数排序）。从 LSD 到 MSD 使后续遍历精炼先前的结果——最终遍历后数组已排序。运行时间为 O(nk)，k 是位数。

核心思想

由于计数排序是稳定的，按第 d 位排序会保留在第 0..d−1 位上相同的元素的相对顺序。处理所有 k 位后，完整的数字顺序建立起来。关键洞察：不需要对完整数字排序——重复地按单个位数排序，稳定性完成其余工作。

执行步骤

1. 找到最大值确定位数 k（= floor(log₁₀(max)) + 1）。
2. 设 exp = 1（个位）。用数字 (x // exp) % 10 作为键，对 arr 运行稳定排序（计数排序）。
3. 设 exp = 10（十位）。对十位数字运行稳定排序。
4. 重复 exp = 100, 1000 … 直到 exp > max。
5. k 次遍历后，数组完全排序。

C++ 参考实现

void countByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> out(n), cnt(10, 0);
    for (int x : arr) cnt[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) cnt[i] += cnt[i-1];
    for (int i = n-1; i >= 0; i--) {
        int d = (arr[i] / exp) % 10;
        out[--cnt[d]] = arr[i];
    }
    arr = out;
}

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countByDigit(arr, exp);
}

复杂度

适用与不适用场景

• 具有有界位宽的大型整数数组（32 位整数、固定长度字符串）。
• 需要不受计数排序范围约束的保证线性排序时。
• 浮点数（需要特殊编码）、变长字符串（填充问题）或内存紧张时应避免。

10. 桶排序

桶排序将元素分配到覆盖值域等子范围的固定数量桶中，独立排序每个桶（通常用插入排序），然后拼接桶。当输入均匀分布时，每个桶平均接收 O(1) 个元素，期望时间 O(n)。

核心思想

若 n 个元素在 [0, 1) 中均匀分布，将每个 x 放入桶 floor(x × n) 意味着平均每个桶接收约 1 个元素。对每个桶用插入排序的期望时间为 O(1)。总期望时间为 O(n)。最坏情况是 O(n²)，若所有元素落入一个桶。

执行步骤

1. 创建 n 个空桶 B[0], B[1], …, B[n−1]。
2. 对 arr 中每个元素 x：插入 B[floor(x × n)]。
3. 用插入排序（或任何小数组排序）对每个非空桶排序。
4. 将所有桶按顺序拼接到输出数组中。

C++ 参考实现

void bucketSort(vector<double>& arr) {
    int n = arr.size();
    vector<vector<double>> buckets(n);
    for (double x : arr) {
        int idx = min((int)(x * n), n - 1);
        buckets[idx].push_back(x);
    }
    int k = 0;
    for (auto& b : buckets) {
        sort(b.begin(), b.end());
        for (double x : b) arr[k++] = x;
    }
}

复杂度

适用与不适用场景

• 已知在 [0, 1) 中均匀分布的浮点数。
• 输入分布已知且大致均匀时。
• 分布偏斜时应避免——大多数元素落入一个桶，退化为 O(n²)。
• 整数排序时应避免——计数排序或基数排序严格更好。

11. 如何选择排序算法

没有一种排序算法在所有场景中都胜出。正确选择取决于数据大小、键是整数还是浮点数、内存约束、稳定性要求和最坏情况保证。将此指南用作决策树。

决策指南

实际应用

• C++ std::sort 使用 IntroSort：快速排序 + 堆排序回退 + 小 n 时插入排序。
• Python list.sort() 和 sorted() 使用 TimSort：自然归并排序 + 插入排序。稳定，最坏 O(n log n)，近乎有序时 O(n)。
• Java Arrays.sort() 对基本类型使用双枢轴快速排序；对对象使用 TimSort（稳定）。
• 数据库 ORDER BY 通常使用外部归并排序处理超过内存的数据。

12. LeetCode 题目模式

排序在 LeetCode 题目中以三种方式出现：实现排序本身、将排序用作预处理来简化更难的问题、或应用快速选择求第 k 顺序统计量。以下是每种模式的经典题目。

实现排序

排序作为预处理

快速选择 / 第 K 顺序

计数 / 基数排序模式