如何用C语言实现桶排序算法？

桶排序是一种非比较型整数排序算法，它通过将元素分布到有限数量的“桶”中，然后对每个桶内的元素单独排序，最后按顺序合并所有桶的结果来完成排序。以下是使用C语言实现桶排序的基本步骤：

1. **初始化桶**：创建一个大小适当的数组，作为桶，每个元素表示一个区间。

2. **元素分配**：遍历输入数组，将每个元素放入对应的桶中，根据元素值计算出应该放入的桶的索引。通常选择合适的步长，如(最大值 - 最小值) / 桶的数量。

3. **桶内排序**：对于每个桶，执行简单的排序算法（如插入排序、冒泡排序等），因为桶里的元素数量较少，容易处理。

4. **合并结果**：从最小索引开始，依次取出每个桶的第一个元素，并添加到结果数组中，直到所有的桶都被处理完。

5. **处理溢出**：如果桶的数量不足以包含数据范围，可能需要预处理一些额外的桶来处理溢出的情况。

下面是一个简化的C语言版本示例：

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

void bucket_sort(int arr[], int n, int max_val, int bucket_size) {
    int *buckets = malloc(n * sizeof(int));
    for (int i = 0; i <= max_val; ++i) {
        buckets[i] = 0;
    }

    // 分配元素到桶
    for (int i = 0; i < n; ++i) {
        buckets[arr[i] / bucket_size]++;
    }

    // 对每个桶内部排序
    int index = 0;
    for (int i = 0; i <= max_val; ++i) {
        while (buckets[i]) {
            arr[index++] = i * bucket_size;
            buckets[i]--;
        }
    }

    free(buckets);
}

// 示例
int main() {
    int arr[] = {5, 8, 1, 9, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_val = *max_element(arr, arr + n);
    bucket_sort(arr, n, max_val, n / 5); // 假设桶大小为n/5

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