桶排序算法实现

桶分类也称为垃圾桶分类。它通过将元素分布到也称为存储桶的数组中来工作。使用不同的排序算法分别对存储桶进行排序。

桶分类的复杂性

算法

• 步骤1开始
• 步骤2设置最初为空的“存储桶”数组。
• 步骤3散点图：遍历原始数组, 将每个对象放入其存储桶中。
• 步骤4对每个非空存储桶进行排序。
• 步骤5收集：按顺序访问存储桶, 然后将所有元素放回到原始数组中。
• 步骤6停止

程序

#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("\nThe array of elements before sorting : \n");
    for (i = 0; i < num; i++)
        printf("%d ", array[i]);  
    printf("\nThe array of elements after sorting : \n"); 
    Bucket_Sort(array, num); 
    for (i = 0; i < num; i++)
        printf("%d ", array[i]);   
    printf("\n");     
    return 0;
}