实现桶排序的C++程序

2023-06-20 22:58:03 69

桶排序技术的复杂性

时间复杂度：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

实现桶排序的C++程序

桶排序技术的复杂性

算法

bucketSort(array,size)

示例代码

热门推荐

随机推荐