桶排序

桶排序（Bucket Sort）是一种线性排序算法，它使用一个或多个“桶”来排序一组数。桶排序的基本思想是将待排序元素分到不同的桶中，对每个桶中的元素进行排序，最后将各个桶中的元素按顺序依次组合起来，即可得到有序序列。

桶排序的具体实现步骤如下：

1. 创建若干个桶。
2. 将待排序的元素分到不同的桶中，具体的方法是按照一定的规则将元素分到不同的桶中。如果待排序的元素是随机分布的，则可以直接将元素分到桶中，每个桶存储的元素的范围是一定的。
3. 对每个桶中的元素进行排序。可以使用其他的排序算法来对每个桶中的元素进行排序，例如插入排序、快速排序等。
4. 将各个桶中的元素按顺序依次组合起来，即可得到有序序列。

桶排序的时间复杂度为O(n)，其中n为待排序元素的个数。桶排序的时间复杂度比较低，但是需要使用较多的额外空间来存储桶。桶的数量、大小以及如何将元素分配到桶中，都会影响桶排序的效率和空间复杂度。

以下是C语言实现的桶排序示例代码：

#include <stdio.h>

void bucket_sort(int arr[], int n, int max_num) {
    int bucket[max_num + 1];
    for (int i = 0; i <= max_num; i++) {
        bucket[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        bucket[arr[i]]++;
    }
    for (int i = 0, j = 0; i <= max_num; i++) {
        while (bucket[i]-- > 0) {
            arr[j++] = i;
        }
    }
}

int main() {
    int arr[] = {8, 5, 3, 9, 1};
    int n = sizeof(arr) / sizeof(int);
    int max_num = 9;
    bucket_sort(arr, n, max_num);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

在这个示例中，我们首先定义了一个大小为max_num+1的桶数组，并将其所有元素都初始化为0。然后，我们对原始数组arr中的每个元素进行计数，并将其放入对应的桶中。最后，我们按照从小到大的顺序遍历桶数组，并将桶中的元素一个一个地放回原始数组中，即可得到排序后的结果。