桶排序

存储桶排序也称为bin 排序。它的工作原理是将元素分配到也称为存储桶的数组中。 桶使用不同的排序算法单独排序。

桶排序的复杂性

算法

第1步，开始
第2步，设置一个最初为空的“桶”(`buckets`)数组。
第3步，分散：遍历原始数组，将每个对象放入其存储桶中。
第4步，对每个非空桶进行排序。
第5步，收集：按顺序访问存储桶并将所有元素放回原始数组中。
第6步，停止

使用C语言实现桶排序算法如下 -

#include <stdio.h>  
void Bucket_Sort(int array[], int n)  
{    
    int i, j;    
    int count[n];   
    for (i = 0; i < n; i++)  
        count[i] = 0;  

    for (i = 0; i < n; i++)  
        (count[array[i]])++;  

    for (i = 0, j = 0; i < n; i++)    
        for(; count[i] > 0; (count[i])--)  
            array[j++] = i;  
}     
/* End of Bucket_Sort() */  

/* The main() begins */  
int main()  
{  
    int array[100], i, num;   

    printf("Enter the size of array : ");     
    scanf("%d", &num);     
    printf("Enter the %d elements to be sorted:n",num);   
    for (i = 0; i < num; i++)  
        scanf("%d", &array[i]);   
    printf("The array of elements before sorting : n");  
    for (i = 0; i < num; i++)  
        printf("%d ", array[i]);    
    printf("The array of elements after sorting : n");   
    Bucket_Sort(array, num);   
    for (i = 0; i < num; i++)  
        printf("%d ", array[i]);     
    printf("n");       
    return 0;  
}

关注微信下载离线手册