桶排序

桶排序（Bucket Sort）

桶排序是计数排序的扩展版本。计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。

每一个桶代表一个区间范围，里面可以承载一个或多个元素。通过划分多个范围相同的区间，将每个子区间自排序，最后合并。桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序的分散优势失效，性能取决于桶内排序算法。

例如一个待排序的序列：

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

确定桶的个数与每个桶的取值范围，遍历待排序序列，将元素放入对应的桶中：

分别对每个桶中的元素进行排序：

将桶中的元素按顺序赋值到原始数组中：

创建桶的数量取决于数据的区间范围，一般创建桶的数量等于待排序的元素数量，下方整数示例代码中，每个桶的区间跨度为：

\left\lfloor \frac{max-min}{buckets} \right\rfloor+1

桶排序

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

typedef int T;

static int cmp(const void *a, const void *b) {
    return (*(const T *)a > *(const T *)b) - (*(const T *)a < *(const T *)b);
}

T *bucket_sort(T *arr, int n) {
    if (n == 0) {
        return arr;
    }

    T max_val = arr[0];
    T min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    int bucket_size = (max_val - min_val) / n + 1;
    T **buckets = (T **)malloc(n * sizeof(T *));
    for (int i = 0; i < n; i++) {
        buckets[i] = (T *)calloc(n + 1, sizeof(T));
    }

    for (int i = 0; i < n; i++) {
        int index = (arr[i] - min_val) / bucket_size;
        buckets[index][0]++;
        buckets[index][buckets[index][0]] = arr[i];
    }

    for (int i = 0; i < n; i++) {
        qsort(buckets[i] + 1, buckets[i][0], sizeof(T), cmp);
    }

    int i = 0;
    for (int j = 0; j < n; j++) {
        for (int k = 1; k <= buckets[j][0]; k++) {
            arr[i++] = buckets[j][k];
        }
    }

    for (int i = 0; i < n; i++) {
        free(buckets[i]);
    }
    free(buckets);

    return arr;
}

int main() {
    int arr[] = {18, 11, 28, 45, 23, 49};
    int n = sizeof(arr) / sizeof(arr[0]);

    bucket_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

上方Lab使用四个宽度为10的桶；代码使用n个桶，两种划分均可正确排序。C示例为每个桶分配n个元素的空间，额外空间为 $O(n^2)$ ；桶内使用比较排序，总时间不是无条件 $O(n)$ 。

题目

所有元素进入同一个桶，算法还能正确排序吗？

题目

为何不能只分桶后按桶编号输出，而完全省略桶内排序？

把[37,12,29,14,32,21]分配到[10,20)、[20,30)、[30,40)三个桶，写出每次分配、各桶排序前后、逐桶合并的结果。只使用这套区间，不另设桶宽。

桶排序（Bucket Sort）

桶排序是计数排序的扩展版本。计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。

例如一个待排序的序列：

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

确定桶的个数与每个桶的取值范围，遍历待排序序列，将元素放入对应的桶中：

分别对每个桶中的元素进行排序：

将桶中的元素按顺序赋值到原始数组中：

创建桶的数量取决于数据的区间范围，一般创建桶的数量等于待排序的元素数量，下方整数示例代码中，每个桶的区间跨度为：

\left\lfloor \frac{max-min}{buckets} \right\rfloor+1

桶排序

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

typedef int T;

static int cmp(const void *a, const void *b) {
    return (*(const T *)a > *(const T *)b) - (*(const T *)a < *(const T *)b);
}

T *bucket_sort(T *arr, int n) {
    if (n == 0) {
        return arr;
    }

    T max_val = arr[0];
    T min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    int bucket_size = (max_val - min_val) / n + 1;
    T **buckets = (T **)malloc(n * sizeof(T *));
    for (int i = 0; i < n; i++) {
        buckets[i] = (T *)calloc(n + 1, sizeof(T));
    }

    for (int i = 0; i < n; i++) {
        int index = (arr[i] - min_val) / bucket_size;
        buckets[index][0]++;
        buckets[index][buckets[index][0]] = arr[i];
    }

    for (int i = 0; i < n; i++) {
        qsort(buckets[i] + 1, buckets[i][0], sizeof(T), cmp);
    }

    int i = 0;
    for (int j = 0; j < n; j++) {
        for (int k = 1; k <= buckets[j][0]; k++) {
            arr[i++] = buckets[j][k];
        }
    }

    for (int i = 0; i < n; i++) {
        free(buckets[i]);
    }
    free(buckets);

    return arr;
}

int main() {
    int arr[] = {18, 11, 28, 45, 23, 49};
    int n = sizeof(arr) / sizeof(arr[0]);

    bucket_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

上方Lab使用四个宽度为10的桶；代码使用n个桶，两种划分均可正确排序。C示例为每个桶分配n个元素的空间，额外空间为 $O(n^2)$ ；桶内使用比较排序，总时间不是无条件 $O(n)$ 。

题目

所有元素进入同一个桶，算法还能正确排序吗？

题目

为何不能只分桶后按桶编号输出，而完全省略桶内排序？

把[37,12,29,14,32,21]分配到[10,20)、[20,30)、[30,40)三个桶，写出每次分配、各桶排序前后、逐桶合并的结果。只使用这套区间，不另设桶宽。

桶排序

桶排序

桶排序（Bucket Sort）

桶排序：分配区间、桶内比较、依次取回

知识测验

知识测验

分桶后仍须桶内排序

桶排序

桶排序

桶排序（Bucket Sort）

桶排序：分配区间、桶内比较、依次取回

知识测验

知识测验

分桶后仍须桶内排序