原理

将元素分布到多个桶中，每个桶内部使用其他排序算法（如插入排序）进行排序，最后将所有桶中的元素合并成一个有序列表。桶排序适用于数据分布均匀的情况，特别适合处理浮点数和小范围整数的排序。桶划分越多，每个桶里面的数据越少，排序时间越短，但相应地占用空间越大。

时间复杂度

最好情况：O(n)，当所有元素均匀分布在各个桶中时。
平均情况：O(n)，当元素分布较为均匀时。
最坏情况：O(n^2)，当所有元素都落在同一个桶中时。

适用场景‌

桶排序适用于数据范围明确且分布较为均匀的情况。当输入数据均匀分布在桶中时，排序效率非常高，时间复杂度接近O(n)，其中n是数组长度。然而，如果数据分布极不均匀，桶排序的效率会大大降低，最坏情况下的时间复杂度接近O(n^2)，特别是当所有元素都落在同一个桶中时。

优缺点‌

优点‌：

当数据分布均匀时，排序效率高。
适用于大量数据的排序，尤其是浮点数的排序。

缺点‌：

数据分布不均匀时，效率低下。
需要额外的空间来创建和存储桶。

实现步骤：

1.设置一个定量的数组当作空桶;
2.遍历输入数据，并且把数据一个一个放到对应的桶里去;
3.对每个不是空的桶进行排序;
4.从不是空的桶里把排好序的数据拼接起来。

C语言案例

#include <stdio.h>
#include <stdlib.h>

/** ↓ ↓ ↓ 插入排序函数（辅助函数） ↓ ↓ ↓ **/
void insertionSort(float arr[], const 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;
    }
}
/** ↑ ↑ ↑ 插入排序函数（辅助函数） ↑ ↑ ↑ **/

// 桶排序函数
/*
1. 确定最大值和最小值：遍历数组，找到最大值和最小值。
2. 创建桶：根据最大值和最小值计算桶的数量和每个桶的大小，创建相应数量的桶。
3. 分配数据到桶：根据每个元素的值，将其分配到对应的桶中。
4. 排序每个桶：对每个桶中的数据使用插入排序进行排序。
5. 合并桶：将所有桶中的数据按顺序合并回原数组。
6. 释放内存：释放分配的内存。
*/
void bucketSort(float arr[], const int numsSize) {
    float max_value = arr[0];
    float min_value = arr[0];
    for (int i = 1; i < numsSize; i++) {
        if (arr[i] > max_value) max_value = arr[i]; // 找到原数组最大值
        if (arr[i] < min_value) min_value = arr[i]; // 找到原数组最小值
    }

    const int bucket_count = numsSize; // 桶的数量
    const float bucketInterval = (max_value - min_value) / bucket_count; // 每个桶存储元素的区间，比如每个桶存储区间为0.9，即每个桶都是以0.9为增量进行存储的。

    // 为桶申请空间
    float **buckets = (float **) malloc(bucket_count * sizeof(float *));
    for (int i = 0; i < bucket_count; i++) {
        buckets[i] = (float *) malloc(numsSize * sizeof(float));
    }
    // calloc用于动态分配内存，calloc会初始化分配的内存为0。这里分配bucket_count个元素，每个元素的大小为sizeof(int)
    // calloc 会分配足够的内存来容纳 num 个大小为 size 的元素，并将分配的内存初始化为零。
    // 具体来说，calloc 会调用 malloc 来分配内存，然后使用 memset 将分配的内存区域设置为零。
    // 此处目的是为每个桶分配一个计数器数组，用于记录每个桶中包含的元素数量。
    // 具体来说，bucket_sizes数组将存储每个桶中元素的数量，以便在后续的排序和合并过程中使用。
    int *bucketEleCountSizes = (int *) calloc(bucket_count, sizeof(int));

    // 分配数据到桶
    for (int i = 0; i < numsSize; i++) {
        // 确定当前元素arr[i]应该放入那个桶中的索引。
        int index = (arr[i] - min_value) / bucketInterval;
        if (index == bucket_count) index--; // 处理等于max_value的情况（边界场景处理）
        // 数组bucketEleCountSizes被初始化为全0，数组中元素数量和桶的数量相等，bucketEleCountSizes[index]初始为0，
        // 也就是说，每个桶中将会从头到尾按顺序进行分配元素。
        // 这样做得好处是，如果有相同值的元素，也会被按顺序放入桶中。如果理解不了，这就是固定写法，记住就行了。
        buckets[index][bucketEleCountSizes[index]] = arr[i];
        bucketEleCountSizes[index]++; // 将第index个桶的元素数量+1,bucketEleCountSizes数组的作用就是记录每个桶的元素数量
    }

    // 排序每个桶
    for (int i = 0; i < bucket_count; i++) {
        insertionSort(buckets[i], bucketEleCountSizes[i]);
    }

    // 合并桶
    int index = 0;
    for (int i = 0; i < bucket_count; i++) {
        for (int j = 0; j < bucketEleCountSizes[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }

    // 释放内存
    for (int i = 0; i < bucket_count; i++) {
        free(buckets[i]);
    }
    free(buckets); // buckets是二维数组，这里没有多重释放
    free(bucketEleCountSizes);
}

int main() {
    float arr[] = {0.78, 0.17, 0.39, 0.21, 0.26, 0.00, 0.21, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
    const int numsSize = sizeof(arr) / sizeof(float);
    printf("排序前：\n");
    for (int i = 0; i < numsSize; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");

    bucketSort(arr, numsSize);

    printf("排序后：\n");
    for (int i = 0; i < numsSize; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码运行结果

排序前：
0.78 0.17 0.39 0.21 0.26 0.00 0.21 0.72 0.94 0.21 0.12 0.23 0.68
排序后：
0.00 0.12 0.17 0.21 0.21 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94