突破 O(n log n)：C语言非比较排序实战

前两篇我们走完了这样一条路：

• 第一篇《C语言常见排序算法详解》：把冒泡、选择、插入、希尔、归并、快速、堆排序写出来，认清它们的时间/空间复杂度和稳定性；
• 第二篇《从会写到会用：C语言排序算法的实战选择与优化》：讲怎么选、怎么优化，用 qsort 做泛型排序，优化快排、规避最坏情况。

但这两篇讲的都是比较排序——通过元素两两比较确定顺序。比较排序有一个理论下界：任何基于比较的排序，最坏情况至少需要 Ω(n log n) 次比较。这由决策树模型可以严格证明。

那么，能不能更快？答案是：能，但前提是放弃"只靠比较"。当我们利用数据的额外信息（如整数范围、位数、分布），就能突破 O(n log n)。这就是本篇的主题——非比较排序。

一、为什么非比较排序能更快？

比较排序的信息论下界成立，是因为它假设"除了比较结果，我们对元素一无所知"。n 个元素有 n! 种排列，决策树至少有 n! 个叶子，树高至少 log₂(n!) ≈ n log n。

非比较排序绕开了这个假设：

• 计数排序利用"元素是 [0, k) 范围内的整数"这一信息，直接用值当数组下标；
• 基数排序利用"整数可以按位拆分"这一结构，逐位分配；
• 桶排序利用"元素近似均匀分布"这一假设，先分桶再桶内排序。

代价是：适用范围变窄。它们不是万能的，用错场景反而更慢。理解"何时能用"比"怎么写"更重要。

二、计数排序（Counting Sort）

适用条件：待排序元素是范围有限的非负整数，最大值 k 不太大（通常 k 与 n 同数量级）。

核心思想：统计每个值出现的次数，再根据次数前缀和直接确定每个元素的位置。

2.1 基础实现（仅排序，不稳定）

#include <stdlib.h>
#include <string.h>

void countingSortSimple(int arr[], int n, int k) {
    // k 为最大值 + 1，即值域 [0, k)
    int *count = (int *)calloc(k, sizeof(int));
    if (!count) return;

    for (int i = 0; i < n; i++) count[arr[i]]++;

    int idx = 0;
    for (int v = 0; v < k; v++) {
        while (count[v]-- > 0) arr[idx++] = v;
    }
    free(count);
}

这个版本简单，但不稳定（相同值无法保持原始顺序），且只能处理非负整数。

2.2 稳定版本（可作为基数排序的子过程）

稳定版本的关键：从后往前遍历原数组，结合前缀和定位，保证相等元素相对顺序不变。

void countingSortStable(int arr[], int n, int k) {
    int *count = (int *)calloc(k, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));
    if (!count || !output) { free(count); free(output); return; }

    // 1. 统计次数
    for (int i = 0; i < n; i++) count[arr[i]]++;

    // 2. 前缀和：count[v] 变为 "值 <= v 的元素个数"
    for (int v = 1; v < k; v++) count[v] += count[v - 1];

    // 3. 从后往前放置，保证稳定
    for (int i = n - 1; i >= 0; i--) {
        int v = arr[i];
        output[--count[v]] = v;  // count[v]-1 是该值最后一个应放的位置
    }

    // 4. 拷回
    memcpy(arr, output, n * sizeof(int));
    free(count);
    free(output);
}

• 时间复杂度：O(n + k)
• 空间复杂度：O(n + k)（稳定版需要输出数组）
• 稳定性：稳定版稳定，简单版不稳定
• 关键点：k 不能太大。若 n = 100 但值域是 [0, 10⁹)，开 10⁹ 的数组直接爆炸，此时应改用基数排序或比较排序。

2.3 处理负数与任意范围

计数排序天然只支持非负整数。若数据含负数或在 [min, max] 区间，可先求 min，把值映射为 arr[i] - min：

void countingSortRange(int arr[], int n) {
    if (n <= 0) return;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    int k = max - min + 1;
    int *count = (int *)calloc(k, sizeof(int));
    if (!count) return;

    for (int i = 0; i < n; i++) count[arr[i] - min]++;
    int idx = 0;
    for (int v = 0; v < k; v++)
        while (count[v]-- > 0) arr[idx++] = v + min;
    free(count);
}

注意：若 max - min 极大（如 32 位整数全范围），此法不可行，请转向基数排序。

三、基数排序（Radix Sort）

适用条件：整数（或可拆成"位"的对象，如定长字符串）。值域可以很大，只要位数有限。

核心思想：按位从低到高（LSD，Least Significant Digit）依次做稳定的计数排序。低位排完，高位排完，整体就有序了。因为每一位的排序是稳定的，前一位的排序结果不会被破坏。

3.1 十进制实现（直观版）

// 对非负整数按十进制位做 LSD 基数排序
void radixSortDecimal(int arr[], int n) {
    if (n <= 0) return;
    int max = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];

    int *output = (int *)malloc(n * sizeof(int));
    int *count = (int *)malloc(10 * sizeof(int));
    if (!output || !count) { free(output); free(count); return; }

    for (long long exp = 1; max / exp > 0; exp *= 10) {
        memset(count, 0, 10 * sizeof(int));

        // 统计当前位数字
        for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

        // 前缀和
        for (int d = 1; d < 10; d++) count[d] += count[d - 1];

        // 从后往前放置，保证稳定
        for (int i = n - 1; i >= 0; i--) {
            int d = (arr[i] / exp) % 10;
            output[--count[d]] = arr[i];
        }
        memcpy(arr, output, n * sizeof(int));
    }
    free(output);
    free(count);
}

• 时间复杂度：O(d × (n + b))，其中 d 为位数，b 为基数（十进制 b=10）。对 32 位整数，d ≤ 10，可视为 O(n)。
• 空间复杂度：O(n + b)
• 稳定性：稳定（依赖每轮计数排序的稳定性）

3.2 二进制/256 进制优化（工程常用）

十进制取模和除法在 CPU 上较慢。工程中常用基数 256（按字节处理），用位运算 >> 和 & 0xFF 替代 / 和 %，32 位整数只需 4 轮：

void radixSort256(int arr[], int n) {
    if (n <= 0) return;
    int *output = (int *)malloc(n * sizeof(int));
    int *count = (int *)malloc(256 * sizeof(int));
    if (!output || !count) { free(output); free(count); return; }

    for (int shift = 0; shift < 32; shift += 8) {
        memset(count, 0, 256 * sizeof(int));
        for (int i = 0; i < n; i++)
            count[(arr[i] >> shift) & 0xFF]++;
        for (int d = 1; d < 256; d++)
            count[d] += count[d - 1];
        for (int i = n - 1; i >= 0; i--) {
            int d = (arr[i] >> shift) & 0xFF;
            output[--count[d]] = arr[i];
        }
        memcpy(arr, output, n * sizeof(int));
    }
    free(output);
    free(count);
}

• 4 轮 × O(n + 256)，常数极小，实测对大量 32 位整数常快于 qsort。
• 注意：上面的写法假定非负整数。对含负数的 int，最高位是符号位，直接按无符号处理会出错。处理方法是：排序前把所有数异或 0x80000000（翻转符号位），排完再异或回来，即可把有符号比较转换为无符号比较。

3.3 处理负数的技巧

// 排序前
for (int i = 0; i < n; i++) arr[i] ^= 0x80000000;  // 翻转符号位
radixSort256(arr, n);                               // 按无符号解释排序
for (int i = 0; i < n; i++) arr[i] ^= 0x80000000;  // 翻回

原理：int 的补码表示中，翻转最高位后，有符号的大小顺序恰好等于无符号的大小顺序。

四、桶排序（Bucket Sort）

适用条件：元素近似均匀分布在某个区间（常见于浮点数 [0, 1)）。

核心思想：把区间划分成若干桶，元素按值落入对应桶，桶内各自排序（常用插入排序），最后按桶顺序拼接。

#include <stdlib.h>

typedef struct { double *data; int size; int cap; } Bucket;

static void bucketPush(Bucket *b, double v) {
    if (b->size == b->cap) {
        b->cap = b->cap ? b->cap * 2 : 4;
        b->data = (double *)realloc(b->data, b->cap * sizeof(double));
    }
    b->data[b->size++] = v;
}

static void insertionSortDouble(double a[], int n) {
    for (int i = 1; i < n; i++) {
        double key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

// 对 [0, 1) 区间内的 double 排序，bucketCount 建议 ≈ n
void bucketSort01(double arr[], int n, int bucketCount) {
    if (n <= 0 || bucketCount <= 0) return;
    Bucket *buckets = (Bucket *)calloc(bucketCount, sizeof(Bucket));

    for (int i = 0; i < n; i++) {
        int idx = (int)(arr[i] * bucketCount);
        if (idx >= bucketCount) idx = bucketCount - 1; // 防止 1.0 越界
        bucketPush(&buckets[idx], arr[i]);
    }

    int k = 0;
    for (int b = 0; b < bucketCount; b++) {
        insertionSortDouble(buckets[b].data, buckets[b].size);
        for (int i = 0; i < buckets[b].size; i++)
            arr[k++] = buckets[b].data[i];
        free(buckets[b].data);
    }
    free(buckets);
}

• 时间复杂度：平均 O(n + k)（k 为桶数，元素均匀分布时每桶约 O(1) 个元素）；最坏 O(n²)（所有元素挤进一个桶，退化为桶内插入排序）。
• 空间复杂度：O(n + k)
• 稳定性：取决于桶内排序；若桶内用插入排序且拼接有序，则稳定。
• 关键点：分布是否均匀决定成败。数据严重倾斜时桶排序会退化，此时不如直接用比较排序。

五、三种非比较排序对比

一句话总结选型：

• 整数且值域不大 → 计数排序；
• 整数但值域很大（如 32 位） → 基数排序（256 进制）；
• 浮点数且分布均匀 → 桶排序；
• 数据分布未知、类型任意 → 回到比较排序（qsort / 快排 / 归并）。

六、实战：什么时候真的值得用非比较排序？

不要为了"炫技"而上非比较排序。它的收益有前提：

1. 数据是整数/定长键，且量足够大（如百万级）。小数据下比较排序的常数优势更明显。
2. 值域或位数可控。计数排序的 k、基数排序的 d 都要在合理范围。
3. 对稳定性有要求且能接受额外内存。基数排序稳定且线性，是"稳定 + 大数据整数排序"的优选。
4. 需要极致性能的特定管线，如日志按时间戳（整数）排序、ID 排序、图像像素直方图相关处理。

反例：对 1000 个随机 double 用桶排序，若分布不均或桶数没调好，可能还不如 qsort。先测量，再优化——这一点和第二篇的性能测试思想一脉相承。

七、常见坑与检查清单

1. 计数排序 k 过大：先检查 max - min，过大就换基数排序。
2. 基数排序稳定性：每一轮必须用稳定的计数排序，且从后往前放置，否则结果错误。
3. 负数处理：基数排序按位处理时，负数会因符号位出错，用异或 0x80000000 翻转或先分离正负。
4. 桶排序越界：arr[i] == 1.0 时 (int)(1.0 * k) == k，需 clamp 到 k - 1。
5. 内存分配失败：malloc/calloc 要判空，尤其 k 或 n 很大时。
6. 不要对浮点数用基数排序：浮点数的位模式不满足"按位排序即大小有序"，除非做特殊变换。
7. 稳定性链条：基数排序/桶排序的稳定性依赖子过程，子过程不稳定则整体不稳定。

八、系列总结：从原理到突破下界

三篇文章构成一条完整的学习路径：

1. 第一篇 · 原理：七种比较排序的写法、复杂度、稳定性——建立基础认知；
2. 第二篇 · 实战：场景选型、qsort 泛型、快排优化、性能测试——把算法用进工程；
3. 第三篇 · 突破：计数/基数/桶排序——利用数据额外信息突破 Ω(n log n) 下界。

核心心法可以浓缩成三句话：

• 比较排序是通用底座，qsort 能覆盖 90% 场景；
• 优化要针对数据特征，有序用插入、重复多三路快排、要稳定用归并；
• 非比较排序是"信息换时间"，用值域/位数/分布信息换取线性时间，但适用范围变窄，必须确认前提。

排序是算法世界的起点，却几乎串起了复杂度分析、分治、数据结构（堆）、泛型编程、工程优化等所有核心主题。把这三种视角（原理、实战、突破）都走一遍，你对"算法工程化"的理解会上一个台阶。