C语言桶排序详解（从零开始掌握高效的线性排序算法）

什么是桶排序？

桶排序（Bucket Sort）是一种分配式排序算法。它的基本思想是：将待排序的元素分到若干个“桶”中，每个桶内部再分别进行排序（可以使用其他排序算法或递归使用桶排序），最后将各个桶中的元素按顺序合并，得到最终的有序序列。

桶排序适用于数据分布比较均匀的情况，例如一组浮点数都在 [0, 1) 区间内。在理想情况下，桶排序的时间复杂度可以达到 O(n)，比传统的 O(n log n) 排序更快！

桶排序的工作原理

假设我们有一组浮点数：[0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]。我们可以这样做：

1. 创建若干个桶（比如10个），编号为0~9；
2. 根据数值大小，将每个数放入对应的桶中（例如 0.42 → 桶4）；
3. 对每个非空的桶内部进行排序（可用插入排序）；
4. 按桶的顺序依次取出所有元素，拼接成最终结果。

C语言桶排序实现

下面我们用C语言来实现一个简单的桶排序程序。为了简化，我们假设输入是一组 [0, 1) 区间的浮点数。

#include <stdio.h>#include <stdlib.h>// 插入排序（用于对单个桶排序）void insertionSort(float arr[], int n) {    for (int i = 1; i < n; i++) {        float key = arr[i];        int j = i - 1;        while (j >= 0 && arr[j] > key) {            arr[j + 1] = arr[j];            j--;        }        arr[j + 1] = key;    }}// 桶排序函数void bucketSort(float arr[], int n) {    // 创建桶（这里用数组的数组模拟）    float **buckets = (float **)malloc(10 * sizeof(float *));    int *bucketCounts = (int *)calloc(10, sizeof(int));    // 初始化每个桶    for (int i = 0; i < 10; i++) {        buckets[i] = (float *)malloc(n * sizeof(float));    }    // 将元素分配到桶中    for (int i = 0; i < n; i++) {        int bucketIndex = (int)(arr[i] * 10);        buckets[bucketIndex][bucketCounts[bucketIndex]] = arr[i];        bucketCounts[bucketIndex]++;    }    // 对每个桶进行排序并合并回原数组    int index = 0;    for (int i = 0; i < 10; i++) {        if (bucketCounts[i] > 0) {            insertionSort(buckets[i], bucketCounts[i]);            for (int j = 0; j < bucketCounts[i]; j++) {                arr[index++] = buckets[i][j];            }        }    }    // 释放内存    for (int i = 0; i < 10; i++) {        free(buckets[i]);    }    free(buckets);    free(bucketCounts);}// 主函数测试int main() {    float arr[] = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};    int n = sizeof(arr) / sizeof(arr[0]);    printf("排序前: ");    for (int i = 0; i < n; i++) {        printf("%.2f ", arr[i]);    }    printf("\n");    bucketSort(arr, n);    printf("排序后: ");    for (int i = 0; i < n; i++) {        printf("%.2f ", arr[i]);    }    printf("\n");    return 0;}

桶排序的优缺点

• 优点：
  • 时间复杂度在理想情况下为 O(n)，非常高效；
  • 稳定排序（如果桶内排序是稳定的）；
  • 适合处理数据分布均匀的大规模数据。
• 缺点：
  • 需要额外的存储空间（桶）；
  • 对数据分布敏感，若数据集中在少数桶中，效率会下降；
  • 不适合整数范围很大的情况（需先归一化）。

总结

通过本教程，你已经掌握了C语言桶排序的基本原理与实现方法。桶排序是一种高效的线性排序算法，在特定场景下表现优异。希望你能动手实践这段代码，加深理解。

记住，学习桶排序算法不仅是为了掌握一种排序方式，更是理解“分而治之”思想的重要一步。如果你正在准备面试或学习数据结构，这个算法绝对值得你深入研究！

相关SEO关键词回顾：

• C语言桶排序
• 桶排序算法
• C语言排序教程
• 桶排序实现