实现桶排序的C++程序
在桶排序技术中,数据项分布在一组桶中。每个桶可以保存相似类型的数据。分配后,每个桶使用另一种排序算法进行排序。之后,所有元素都被收集到主列表中以获得排序形式。
桶排序技术的复杂性
时间复杂度:O(n+k)表示最佳情况和平均情况,O(n2)表示最坏情况。
空间复杂度:O(nk)最坏情况
Input − A list of unsorted data: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 Output − 排序后的数组: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
算法
bucketSort(array,size)
输入:一个数据数组,以及数组中的总数
输出:排序后的数组
Begin for i := 0 to size-1 do insert array[i] into the bucket index (size * array[i]) done for i := 0 to size-1 do sort bucket[i] done for i := 0 to size -1 do gather items of bucket[i] and put in array done End
示例代码
#include输出结果#include #include using namespace std; void display(float *array, int size) { for(int i = 0; i bucket[size]; for(int i = 0; i > n; float arr[n]; //创建具有给定元素数量的数组 cout << "输入元素:" << endl; for(int i = 0; i > arr[i]; } cout << "排序前的数组: "; display(arr, n); bucketSort(arr, n); cout << "排序后的数组: "; display(arr, n); }
输入元素数量: 10 输入元素: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 排序前的数组: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 排序后的数组: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79