桶排序算法实现桶排序算法|数据结构

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

算法	复杂
Space	O(1)
最差的情况	O(n2)
最好的情况	Ω（n + k）
平均情况	θ(n+k)

算法

步骤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; }