C语言实现桶排序的方法示例

桶排序是一种非常高效的排序算法，它的基本思想是将要排序的数据分到几个有序的桶中，每个桶内部再完成排序，最终按照桶的顺序依次连接起来。在本文中，我们将详细讲解如何使用C语言实现桶排序，并提供两个示例来帮助读者更好地理解它的实现过程。

实现步骤

桶排序的实现过程主要分为以下几个步骤：

1. 创建桶：根据待排序数组的最大值和最小值，确定需要创建多少个桶，并全部初始化为空；
2. 分配数据：遍历待排序数组，根据每个数据值的范围，将数据分配到对应的桶中；
3. 数据排序：对每个桶内的数据进行排序，可以使用任何一种排序算法；
4. 合并数据：按照桶的顺序，将所有桶中的数据依次合并起来。

以下是C语言实现桶排序的完整代码：

#include <stdio.h>
#include <stdlib.h>
#define BUCKET_SIZE 10

//定义桶的结构体
typedef struct bucket {
    int size;
    int data[BUCKET_SIZE];
} Bucket;

void bucket_sort(int array[], int size) {
    //找到最大值最小值，确定桶的数量
    int max = array[0], min = array[0];
    for(int i=1; i<size; i++) {
        if(array[i]>max) {
            max = array[i];
        }
        if(array[i]<min) {
            min = array[i];
        }
    }
    int bucket_count = (max-min)/BUCKET_SIZE + 1;

    //创建桶并初始化为空
    Bucket* buckets = (Bucket*)malloc(bucket_count*sizeof(Bucket));
    for(int i=0; i<bucket_count; i++) {
        buckets[i].size = 0;
    }

    //将数据分配到对应的桶中
    for(int i=0; i<size; i++) {
        int bucket_index = (array[i]-min)/BUCKET_SIZE;
        buckets[bucket_index].data[buckets[bucket_index].size] = array[i];
        buckets[bucket_index].size++;
    }

    //对每个桶内的数据进行排序
    for(int i=0; i<bucket_count; i++) {
        for(int j=0; j<buckets[i].size-1; j++) {
            for(int k=0; k<buckets[i].size-j-1; k++) {
                if(buckets[i].data[k]>buckets[i].data[k+1]) {
                    int temp = buckets[i].data[k];
                    buckets[i].data[k] = buckets[i].data[k+1];
                    buckets[i].data[k+1] = temp;
                }
            }
        }
    }

    //按照桶的顺序，将所有桶中的数据依次合并起来
    int index = 0;
    for(int i=0; i<bucket_count; i++) {
        for(int j=0; j<buckets[i].size; j++) {
            array[index] = buckets[i].data[j];
            index++;
        }
    }

    free(buckets);
}

int main() {
    int array1[] = {3, 2, 1, 5, 4, 9, 8, 7, 6, 0};
    int size1 = sizeof(array1)/sizeof(int);

    bucket_sort(array1, size1);

    printf("After sorting: ");
    for(int i=0; i<size1; i++) {
        printf("%d ", array1[i]);
    }
    printf("\n");

    int array2[] = {30, 22, 14, 15, 3, 9, 17, 28, 18, 12};
    int size2 = sizeof(array2)/sizeof(int);

    bucket_sort(array2, size2);

    printf("After sorting: ");
    for(int i=0; i<size2; i++) {
        printf("%d ", array2[i]);
    }
    printf("\n");

    return 0;
}

示例说明

示例一

假设我们需要对如下数组进行排序：

3, 2, 1, 5, 4, 9, 8, 7, 6, 0

首先，我们遍历整个数组，找到最大值和最小值：

int max = array[0], min = array[0];
for(int i=1; i<size; i++) {
    if(array[i]>max) {
        max = array[i];
    }
    if(array[i]<min) {
        min = array[i];
    }
}

此时，最大值为9，最小值为0。由于我们设置桶的大小为10，因此一共需要创建1个容量为10的桶。

int bucket_count = (max-min)/BUCKET_SIZE + 1;
Bucket* buckets = (Bucket*)malloc(bucket_count*sizeof(Bucket));

接下来，我们将每个数据分配到对应的桶中：

for(int i=0; i<size; i++) {
    int bucket_index = (array[i]-min)/BUCKET_SIZE;
    buckets[bucket_index].data[buckets[bucket_index].size] = array[i];
    buckets[bucket_index].size++;
}

例如，数值为3的数据将会被存储在编号为0的桶中。

然后，我们需要对每个桶内的数据进行排序：

for(int i=0; i<bucket_count; i++) {
    for(int j=0; j<buckets[i].size-1; j++) {
        for(int k=0; k<buckets[i].size-j-1; k++) {
            if(buckets[i].data[k]>buckets[i].data[k+1]) {
                int temp = buckets[i].data[k];
                buckets[i].data[k] = buckets[i].data[k+1];
                buckets[i].data[k+1] = temp;
            }
        }
    }
}

最后，我们按照桶的顺序，将所有桶中的数据依次合并起来：

int index = 0;
for(int i=0; i<bucket_count; i++) {
    for(int j=0; j<buckets[i].size; j++) {
        array[index] = buckets[i].data[j];
        index++;
    }
}

此时，数组已经被排好序：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

示例二

假设我们需要对如下数组进行排序：

30, 22, 14, 15, 3, 9, 17, 28, 18, 12

首先，我们遍历整个数组，找到最大值和最小值：

int max = array[0], min = array[0];
for(int i=1; i<size; i++) {
    if(array[i]>max) {
        max = array[i];
    }
    if(array[i]<min) {
        min = array[i];
    }
}

此时，最大值为30，最小值为3。由于我们设置桶的大小为10，因此一共需要创建3个容量为10的桶。

int bucket_count = (max-min)/BUCKET_SIZE + 1;
Bucket* buckets = (Bucket*)malloc(bucket_count*sizeof(Bucket));

接下来，我们将每个数据分配到对应的桶中：

for(int i=0; i<size; i++) {
    int bucket_index = (array[i]-min)/BUCKET_SIZE;
    buckets[bucket_index].data[buckets[bucket_index].size] = array[i];
    buckets[bucket_index].size++;
}

例如，数值为30的数据将会被存储在编号为2的桶中。

然后，我们需要对每个桶内的数据进行排序：

for(int i=0; i<bucket_count; i++) {
    for(int j=0; j<buckets[i].size-1; j++) {
        for(int k=0; k<buckets[i].size-j-1; k++) {
            if(buckets[i].data[k]>buckets[i].data[k+1]) {
                int temp = buckets[i].data[k];
                buckets[i].data[k] = buckets[i].data[k+1];
                buckets[i].data[k+1] = temp;
            }
        }
    }
}

最后，我们按照桶的顺序，将所有桶中的数据依次合并起来：

int index = 0;
for(int i=0; i<bucket_count; i++) {
    for(int j=0; j<buckets[i].size; j++) {
        array[index] = buckets[i].data[j];
        index++;
    }
}

此时，数组已经被排好序：

3, 9, 12, 14, 15, 17, 18, 22, 28, 30

以上就是C语言实现桶排序的完整攻略和两个示例的详细说明。