非比较排序算法实现：原理与代码示例

在处理大量数据时，传统基于比较的排序算法如快排、归并虽然常见，但时间复杂度受限于 O(n log n)。有没有更快的方式？答案是有的——非比较排序算法。它们不通过元素间的两两比较来决定顺序，而是利用数据本身的特性，实现线性甚至更优的时间复杂度。

计数排序（Counting Sort）

当待排序的整数范围不大时，计数排序非常高效。它的思路很简单：统计每个数值出现的次数，然后按顺序输出。比如你有一组学生成绩（0~100分），想快速排好序，用这个方法再合适不过。

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    int *count = (int*)calloc(max + 1, sizeof(int));

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

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

这段 C 代码展示了如何对一个整型数组进行计数排序。注意它只适用于非负整数，且最大值不能太大，否则会占用过多内存。

基数排序（Radix Sort）

如果数字范围很大，比如要排手机号或身份证号，计数排序就不现实了。这时候可以考虑基数排序。它从个位开始，逐位使用稳定排序（通常是计数排序）处理每一位，直到最高位。

想象你在整理一叠发票，先按最后一位数字分堆，再按倒数第二位合并重排，最终得到有序结果。这就是基数排序的思想。

int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    return max;
}

void countSortForRadix(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

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

void radixSort(int arr[], int n) {
    int max = getMax(arr, n);
    for (int exp = 1; max / exp > 0; exp *= 10)
        countSortForRadix(arr, n, exp);
}

桶排序（Bucket Sort）

当数据分布较为均匀时，桶排序表现优异。它把数据划分到多个“桶”里，每个桶内单独排序，最后依次合并。就像你把一堆杂乱的快递按区域放进不同货架，再各自理清楚。

例如浮点数在 [0,1) 范围内时，可以创建 10 个桶，将 0.23 放入第 2 个桶，0.78 放入第 7 个，以此类推。

这些算法虽然不依赖比较，但也各有局限。计数排序受限于数值范围，基数排序对字符串和整数友好但实现稍复杂，桶排序则依赖数据分布。选择哪种方式，得看手头的数据长什么样。