使用c语言实现桶排序

桶排序是一种线性时间复杂度的排序算法，适用于待排序元素均匀分布在一个范围内的情况。下面是使用C语言实现桶排序的基本步骤：

1. 确定待排序数组的最大值和最小值，并计算出待排序数组的范围。
2. 创建一个桶数组，桶的数量为待排序数组的范围大小。
3. 遍历待排序数组，将每个元素放入对应的桶中。
4. 对每个非空的桶进行排序，可以使用插入排序等简单的排序算法。
5. 将所有非空桶中的元素按顺序合并到原始数组中。

下面是一个使用C语言实现桶排序的示例代码：

#include <stdio.h>

// 桶排序函数
void bucketSort(int arr[], int n) {
    // 找到最大值和最小值
    int maxVal = arr[0];
    int minVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }

    // 计算桶的数量
    int bucketCount = maxVal - minVal + 1;

    // 创建桶数组
    int *buckets = (int *)malloc(bucketCount * sizeof(int));
    memset(buckets, 0, bucketCount * sizeof(int));

    // 将元素放入桶中
    for (int i = 0; i < n; i++) {
        buckets[arr[i] - minVal]++;
    }

    // 合并桶中的元素到原始数组中
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        while (buckets[i] > 0) {
            arr[index++] = i + minVal;
            buckets[i]--;
        }
    }

    // 释放桶数组的内存
    free(buckets);
}

int main() {
    int arr[] = {5, 2, 8, 9, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bucketSort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}