排序：从平方级到线性级

问题#

给定序列 $a_0,a_1,\ldots,a_{n-1}$，把它按非降顺序排列。排序算法的差别不只在速度，还在它需要的额外空间、是否稳定，以及是否依赖较小的值域。

算法	最坏时间	额外空间	稳定	适合场景
选择排序	$O(n^2)$	$O(1)$	否	教学、小数据、交换代价高
插入排序	$O(n^2)$	$O(1)$	是	小数据或近乎有序
冒泡排序	$O(n^2)$	$O(1)$	是	教学；实际很少作为首选
归并排序	$O(n\log n)$	$O(n)$	是	稳定排序、统计逆序对
快速排序	$O(n^2)$	平均 $O(\log n)$	否	通用内存排序；平均很快
计数排序	$O(n+W)$	$O(W)$	可稳定	整数值域 $W$ 较小
桶排序	平均 $O(n+k)$	$O(n+k)$	取决于桶内排序	数据分布较均匀
基数排序	$O(d(n+b))$	$O(n+b)$	是	固定位数的非负整数

比较排序只通过元素间比较获取顺序信息，因此一般情形下存在 $\Omega(n\log n)$ 的比较次数下界。计数、桶和基数排序绕开了纯比较模型，但换来了对值域或表示形式的要求。

核心思想与不变量#

三种平方级排序#

• 选择排序：第 $i$ 轮开始前，区间 $[0,i)$ 已经是全局最小的 $i$ 个元素；在后缀中找到最小值放到位置 $i$。
• 插入排序：第 $i$ 轮开始前，区间 $[0,i)$ 已经有序；把 $a_i$ 向左插入到正确位置。只在严格大于时移动，便可保持稳定。
• 冒泡排序：每完成一轮，相邻逆序对被交换，当前未排序部分的最大值被送到末尾；若一轮没有交换，数组已经有序。

两种分治排序#

• 归并排序：递归排序左右半区，再用双指针合并两个有序序列。合并时，若右半元素先被取出，它与左半尚未取出的所有元素构成逆序对。
• 快速排序：选取枢轴并完成划分，使小于、等于、大于枢轴的元素分居三个区间，再递归处理两侧。三路划分能避免大量重复值令递归极度失衡。

三种非比较排序#

• 计数排序：count[x] 记录值 $x$ 出现多少次，再按值域顺序还原答案。
• 桶排序：用映射规则把数分到若干桶中，桶内排序后依次拼接；效果取决于分桶是否均衡。
• LSD 基数排序：从最低位到最高位反复做稳定排序。处理完前 $t$ 位后，序列已经按这 $t$ 位组成的键有序。

复杂度#

选择、插入和冒泡排序最坏均为 $O(n^2)$；插入和带提前退出的冒泡在已有序时可到 $O(n)$。归并排序始终是 $O(n\log n)$，快速排序平均为 $O(n\log n)$、最坏为 $O(n^2)$。

若值域宽度为 $W$，计数排序是 $O(n+W)$。桶排序设桶数为 $k$，理想均匀分布时接近 $O(n+k)$，极端集中时退化。基数排序若有 $d$ 位、每位基数为 $b$，复杂度为 $O(d(n+b))$。

C++17 模板#

下面是一份可独立编译的模板。计数与桶排序支持负整数；LSD 基数排序的模板明确只接收非负整数。merge_sort 在排序的同时返回逆序对数量。

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

using namespace std;

void selection_sort(vector<int>& a) {
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        int best = i;
        for (int j = i + 1; j < static_cast<int>(a.size()); ++j) {
            if (a[j] < a[best]) best = j;
        }
        swap(a[i], a[best]);
    }
}

void insertion_sort(vector<int>& a) {
    for (int i = 1; i < static_cast<int>(a.size()); ++i) {
        int value = a[i];
        int j = i;
        while (j > 0 && a[j - 1] > value) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = value;
    }
}

void bubble_sort(vector<int>& a) {
    for (int right = static_cast<int>(a.size()) - 1; right > 0; --right) {
        bool changed = false;
        for (int i = 0; i < right; ++i) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                changed = true;
            }
        }
        if (!changed) break;
    }
}

long long merge_sort_impl(vector<int>& a, vector<int>& buffer, int left, int right) {
    if (right - left <= 1) return 0;
    int middle = left + (right - left) / 2;
    long long inversions = merge_sort_impl(a, buffer, left, middle)
                         + merge_sort_impl(a, buffer, middle, right);

    int i = left, j = middle, out = left;
    while (i < middle && j < right) {
        if (a[i] <= a[j]) {
            buffer[out++] = a[i++];
        } else {
            buffer[out++] = a[j++];
            inversions += middle - i;
        }
    }
    while (i < middle) buffer[out++] = a[i++];
    while (j < right) buffer[out++] = a[j++];
    for (int p = left; p < right; ++p) a[p] = buffer[p];
    return inversions;
}

long long merge_sort(vector<int>& a) {
    vector<int> buffer(a.size());
    return merge_sort_impl(a, buffer, 0, static_cast<int>(a.size()));
}

void quick_sort_impl(vector<int>& a, int left, int right) {
    if (left >= right) return;
    int pivot = a[left + (right - left) / 2];
    int less = left, current = left, greater = right;

    while (current <= greater) {
        if (a[current] < pivot) swap(a[less++], a[current++]);
        else if (a[current] > pivot) swap(a[current], a[greater--]);
        else ++current;
    }
    quick_sort_impl(a, left, less - 1);
    quick_sort_impl(a, greater + 1, right);
}

void quick_sort(vector<int>& a) {
    if (!a.empty()) quick_sort_impl(a, 0, static_cast<int>(a.size()) - 1);
}

void counting_sort(vector<int>& a) {
    if (a.empty()) return;
    auto [minimum_it, maximum_it] = minmax_element(a.begin(), a.end());
    long long width = 1LL * (*maximum_it) - (*minimum_it) + 1;
    if (width > 20'000'000) {
        throw runtime_error("value range is too large for counting sort");
    }

    vector<int> count(static_cast<size_t>(width), 0);
    for (int value : a) ++count[value - *minimum_it];

    int out = 0;
    for (int offset = 0; offset < static_cast<int>(count.size()); ++offset) {
        while (count[offset]-- > 0) a[out++] = *minimum_it + offset;
    }
}

void bucket_sort(vector<int>& a, int bucket_width) {
    if (a.empty()) return;
    if (bucket_width <= 0) throw invalid_argument("bucket_width must be positive");

    auto [minimum_it, maximum_it] = minmax_element(a.begin(), a.end());
    long long bucket_count = (1LL * (*maximum_it) - (*minimum_it)) / bucket_width + 1;
    if (bucket_count > 1'000'000) {
        throw runtime_error("too many buckets");
    }

    vector<vector<int>> buckets(static_cast<size_t>(bucket_count));
    for (int value : a) {
        buckets[(1LL * value - *minimum_it) / bucket_width].push_back(value);
    }

    int out = 0;
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
        for (int value : bucket) a[out++] = value;
    }
}

void radix_sort(vector<uint32_t>& a) {
    if (a.empty()) return;
    uint32_t maximum = *max_element(a.begin(), a.end());
    vector<uint32_t> output(a.size());

    for (uint64_t place = 1; place <= maximum; place *= 10) {
        int count[10] = {};
        for (uint32_t value : a) ++count[(value / place) % 10];
        for (int digit = 1; digit < 10; ++digit) count[digit] += count[digit - 1];
        for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
            int digit = (a[i] / place) % 10;
            output[--count[digit]] = a[i];
        }
        a.swap(output);
        if (place > maximum / 10) break;
    }
}

int main() {
    vector<int> values = {5, -1, 3, 3, 0, 8, 2};
    long long inversions = merge_sort(values);
    for (int value : values) cout << value << ' ';
    cout << "\ninversions = " << inversions << '\n';
    return 0;
}

示例#

对序列 5 -1 3 3 0 8 2 调用 merge_sort，输出：

-1 0 2 3 3 5 8
inversions = 10

以归并过程为例：左右两段已经分别有序时，只需比较两段的当前首元素；每次取走较小者，因此已经写入缓冲区的前缀始终有序。

易错点#

1. 归并时用 <= 从左段取相等元素，才能保持稳定；统计逆序对时，相等元素不能计入。
2. 快排若永远取端点作枢轴，在有序输入上可能退化到 $O(n^2)$；随机枢轴或三路划分更稳健。
3. 计数排序的关键限制是值域宽度，不只是元素数量；先用 64 位计算 max - min + 1，避免溢出和爆内存。
4. LSD 基数排序的每一轮必须稳定，否则低位已经建立的顺序会被破坏。
5. 桶排序没有脱离分布假设；所有元素落入同一桶时不会获得理想复杂度。
6. 空数组下 size() - 1 会产生无符号下溢，转换或递归前要先判断为空。

工具选择与延伸阅读#

• std::sort 是日常首选的不稳定通用排序；需要稳定性时使用 std::stable_sort。
• 插入排序常用于小区间，实际的混合排序会在递归规模很小时切换到它。
• 归并排序可自底向上实现，避免递归；它也天然适合链表和外部排序。
• MSD 基数排序从最高位开始递归分桶；LSD 则从最低位开始，要求每轮稳定。
• 延伸阅读（非课程主线）：如果只需第 $k$ 小值而不要求整体有序，可考虑 std::nth_element，其底层属于选择问题，平均复杂度为 $O(n)$。