Sort

排序是所有算法的前置步骤

排序本身很少是目的,更多是手段——排完序之后:

  • 二分查找成为可能
  • 双指针成为可能
  • 贪心策略有了明确的顺序
  • 相同元素聚在一起(去重、计数)

**"先排序再说"**是解题时最常用的一步。

比较排序

总览

算法平均最坏最好空间稳定原地
冒泡排序O(n2)O(n^2)O(n2)O(n^2)O(n)O(n)O(1)O(1)✓✓
选择排序O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)✗✓
插入排序O(n2)O(n^2)O(n2)O(n^2)O(n)O(n)O(1)O(1)✓✓
希尔排序O(n1.3)O(n^{1.3})O(n2)O(n^2)O(n)O(n)O(1)O(1)✗✓
归并排序O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(n)O(n)✓✗
快速排序O(nlog⁡n)O(n\log n)O(n2)O(n^2)O(nlog⁡n)O(n\log n)O(log⁡n)O(\log n)✗✓
堆排序O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(1)O(1)✗✓
计数排序O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(k)O(k)✓✗
基数排序O(d(n+k))O(d(n+k))——O(n+k)O(n+k)✓✗
桶排序O(n+k)O(n+k)O(n2)O(n^2)—O(n+k)O(n+k)✓✗

冒泡排序

反复交换相邻逆序对,每轮把最大的"浮"到末尾。

void bubble_sort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;      // 已有序,提前退出
    }
}

唯一价值:教学。swapped 优化让最好情况(已有序)是O(n)O(n)。实际不用。

选择排序

每轮找未排序部分的最小值,放到当前位置。

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

不稳定:swap 会把前面的元素换到后面。例:[2a, 2b, 1] → 第一轮 [1, 2b, 2a],两个 2 的相对顺序变了。

特点:比较次数固定n2/2n^2/2,但交换次数只有O(n)O(n)——交换代价高的场景有价值(罕见)。

插入排序

把每个元素插到前面已排序部分的正确位置。

void insertion_sort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];      // 后移,不是交换
            j--;
        }
        a[j + 1] = key;
    }
}

稳定:a[j] > key 而不是 >=,相等时不移动。

实际很重要:

  • 小规模(n<50n < 50)时比快排快(常数小、无递归、缓存友好)
  • 近乎有序的数据上是O(n)O(n)
  • 所以所有工业级排序在小数组上都退化成插入排序(std::sort 在n≤16n \le 16 时用插入排序)

希尔排序

分组插入排序,间隔逐步缩小。

void shell_sort(vector<int>& a) {
    int n = a.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i], j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

优势:O(1)O(1) 空间、原地、代码短,平均O(n1.3)O(n^{1.3})。嵌入式或内存受限场景有用。

归并排序

见分治章节。核心是合并两个有序段。

  • 唯一稳定的O(nlog⁡n)O(n \log n) 比较排序(无需额外分配的稳定排序)
  • 缺点:需要O(n)O(n) 辅助空间
  • 外部排序的主力:数据放不下内存时,归并是唯一可行(只需顺序读)

快速排序

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r];
    int i = l;
    for (int j = l; j < r; j++)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], r);
    return i;
}

void quick_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quick_sort(a, l, p - 1);
    quick_sort(a, p + 1, r);
}

性能关键在 pivot 选择:

策略最坏场景效果
总选 a[r]已排序数组 →O(n2)O(n^2)差
随机选随机数据好,可被构造卡中
三数取中(median-of-three)常见有序模式 OK好
取真正的中位数不可能(代价高)—

优化:

  1. 小区间用插入排序(n≤16n \le 16)
  2. 三数取中选 pivot
  3. 尾递归消除:先递归小的那半,大的那半用循环(保证栈深O(log⁡n)O(\log n))
  4. 三路划分(处理大量重复元素,见下)

三路划分(处理重复元素)

// 数组分成 [< pivot][== pivot][> pivot] 三段
void quick_sort3(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l + (r - l) / 2];
    int i = l, j = l, k = r;
    while (j <= k) {
        if      (a[j] < pivot) swap(a[i++], a[j++]);
        else if (a[j] > pivot) swap(a[j], a[k--]);
        else                   j++;
    }
    quick_sort3(a, l, i - 1);
    quick_sort3(a, k + 1, r);
}

价值:全是相同元素时,普通快排是O(n2)O(n^2)(每次只减少 1),三路划分是O(n)O(n)。

堆排序

void sift_down(vector<int>& a, int i, int n) {
    while (true) {
        int l = 2 * i + 1, r = l + 1, mx = i;
        if (l < n && a[l] > a[mx]) mx = l;
        if (r < n && a[r] > a[mx]) mx = r;
        if (mx == i) break;
        swap(a[i], a[mx]);
        i = mx;
    }
}

void heap_sort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n);   // 建堆 O(n)
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);        // 最大元素换到末尾
        sift_down(a, 0, i);      // 恢复堆
    }
}
  • 原地、O(1)O(1) 额外空间、最坏O(nlog⁡n)O(n \log n)
  • 不稳定、缓存不友好(跳跃访问)
  • 建堆是O(n)O(n) 不是O(nlog⁡n)O(n \log n)——因为大部分节点在底层,下沉距离短

为什么实际不如快排:缓存局部性差。但在要求最坏保证和只需前 k 个的场景有用。

非比较排序

计数排序

元素值域小(0∼k0 \sim k)时,统计每个值出现次数。

void counting_sort(vector<int>& a, int k) {
    vector<int> cnt(k + 1, 0);
    for (int x : a) cnt[x]++;
    for (int i = 1; i <= k; i++) cnt[i] += cnt[i - 1];   // 前缀和 → 每个值的最终位置
    vector<int> out(a.size());
    for (int i = (int)a.size() - 1; i >= 0; i--)         // 从后往前保证稳定
        out[--cnt[a[i]]] = a[i];
    a = out;
}

O(n+k)O(n + k),突破Ω(nlog⁡n)\Omega(n \log n) 下界——因为它不基于比较,用了"值是小整数"这个额外信息。

为什么从后往前遍历:保证稳定性(先处理后面的,相同元素保持原相对顺序)。

基数排序

按位(个位 → 十位 → 百位…)分别做稳定的计数排序。

void radix_sort(vector<int>& a) {
    const int B = 1 << 8;          // 每 8 位一轮
    int n = a.size();
    vector<int> tmp(n);
    for (int shift = 0; shift < 32; shift += 8) {
        vector<int> cnt(B + 1, 0);
        for (int x : a) cnt[((x >> shift) & (B - 1)) + 1]++;
        for (int i = 1; i <= B; i++) cnt[i] += cnt[i - 1];
        for (int x : a) tmp[cnt[(x >> shift) & (B - 1)]++] = x;
        a.swap(tmp);
    }
}

O(d⋅(n+B))O(d \cdot (n + B)),dd 是位数/轮数。对 32 位整数、8 位一轮 → 4 轮。

特点:

  • 比快排快(当nn 大且值域小时)
  • 稳定
  • 需要额外空间

注意负数:要特殊处理(加偏移或先分离正负)。

桶排序

把值域分成若干桶,桶内排序,再串联。

  • 数据均匀分布时O(n)O(n)
  • 最坏(全落一个桶)退化到桶内算法的复杂度

比较排序的下界

任何基于比较的排序,最坏至少Ω(nlog⁡n)\Omega(n \log n) 次比较。

证明(决策树):

n 个元素有 n! 种排列
每次比较最多把可能性分成 2 份
决策树需要至少 n! 个叶子

树高 h 满足 2^h >= n!
→ h >= log2(n!) = Ω(n log n)   (Stirling 公式)

推论:

  • 归并、快排、堆排序在渐近意义下已经最优
  • 要更快必须不基于比较(计数、基数、桶)

C++ 标准库

#include <algorithm>

// 1. sort:内省排序(Introsort)
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
sort(v.begin(), v.end(), [](const Item& a, const Item& b) {
    if (a.x != b.x) return a.x < b.x;      // 多关键字:先比 x
    return a.y < b.y;                      // 再比 y
});

// 2. stable_sort:稳定(归并),O(n log n),必要时 O(n log^2 n)
stable_sort(v.begin(), v.end());

// 3. partial_sort:只保证前 k 个有序,O(n log k)
partial_sort(v.begin(), v.begin() + k, v.end());

// 4. nth_element:保证第 n 个位置是"如果全排序会在那的元素",O(n) 平均
nth_element(v.begin(), v.begin() + n / 2, v.end());   // 求中位数用这个
int median = v[n / 2];

// 5. 有序性检查
bool ok = is_sorted(v.begin(), v.end());

std::sort 的实现(Introsort):

1. 快排(三数取中 pivot)
2. 递归深度超过 2*log(n) → 切换到堆排序(防止快排退化到 O(n^2))
3. 子数组 <= 16 → 插入排序

这是工业级排序的标准答案:结合了三种算法各自的优点。

比较函数的要求

必须是严格弱序(strict weak ordering):

// 要求:
comp(a, a) == false           // 非自反
comp(a, b) && comp(b, a) 不能同时为真   // 非对称
comp(a,b) && comp(b,c) ⇒ comp(a,c)     // 传递

// 错误示范(会导致 UB,可能崩溃)
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });   // 错!a==b 时返回 true

经典 bug:用 <= 而不是 <。这会让 comp(a,a) == true,破坏严格弱序,导致越界访问。

排序作为其他算法的工具

用途做法
去重排序后相邻比较,unique
计数排序后统计连续段长度
双指针排序后两数之和、区间问题
二分排序后才能二分
贪心排序确定处理顺序
离散化排序 + 去重 + 二分映射
扫描线按坐标排序,依次处理事件

离散化(常用模板)

vector<int> xs = a;                                  // 复制
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());    // 去重
// 值 x 映射到的下标(0-based)
int id = lower_bound(xs.begin(), xs.end(), x) - xs.begin();

用途:值域很大(10910^9)但元素个数少(10510^5)时,压缩到[0,n)[0, n) 以便用数组/树状数组。

常见坑

  • 比较函数用 <=:破坏严格弱序,UB
  • 排序后忘了去重就二分:重复元素不影响二分正确性,但计数会错
  • 结构体排序的比较函数漏了某个关键字:导致不稳定行为
  • nth_element 不保证前 k 个有序:只保证第 n 个位置正确且左边的都不大于它
  • 基数排序处理负数:需要先偏移
  • 以为 sort 是稳定的:不是。要稳定用 stable_sort 或在比较函数里加"原下标"作为最后的关键字
  • 对大对象排序的拷贝开销:用指针/索引排序,或给结构体实现移动语义
  • 排序键为浮点:避免直接比较相等,用 eps
  • 稳定排序的意义:多关键字排序时,可以按次要关键字先排一次,再用稳定排序排主关键字