算法-桶排序(Bucket sort)

时间：2023-07-16 11:04:02

本文由@呆代待殆原创，转载请注明出处。

简介：这个排序算法不属于比较排序，在平均情况下他的时间代价是O(n)，并且它假设它的输入数据均匀的分布在一个固定的区间里。

思路：桶排序假设他的输入均匀的分布在一个固定的区间，并且它将这个区间划分成均匀的子区间，每个子区间称为一个桶，然后将输入的数据分别放到对应的桶里，再对每个桶中的数据进行单独的排序（或者对每个单独的桶再进行桶排序的递归调用，直到任何桶都只有一个数据），然后遍历输出每个桶里的数据就是最后的排序结果。

算法分析

平均时间复杂度：Θ(n)

空间复杂度：O(n+m) n是输入数据量，m是桶的数量

稳定性：稳定算法

是否是原址排序：否

代码实现

关于桶排序的实现，我们要解决两个问题

1，确定桶的数量，并把数据放到对应的桶里。

2，对每个桶里的数据进行排序。

对于问题一，我们假设我们的输入是[0,max]范围内的数，max需要当做参数输入，并规定我们的算法再任何情况下都用10个桶实现。那么我们确定数据的属于哪个桶时的算法如下

 int putAt(int n,int max){

     int i = ;

     while (i < ){

         if (n > max*i /  && n < max*(i + ) / )//将0~max划分成10个区间，把数放到这些对应的区间里，区间号就是桶的编号

             return i;

         ++i;

     }

     return i;

 }

对于问题二，我们采用插入排序分别对每个桶进行排序，这里给出代码，插入排序介绍传送门

 void insert_sort(vector<int>& v){

     int temp;

     for (int i = ; i < v.size(); ++i){//从第二个数据开始

         temp = v[i];//在数组中挖一个坑，将坑里的数据放在temp中

         int j = i - ;

         while (j> && temp < v[j]){//依次和坑前的数据对比，把所有比temp大的数往右挪一位（就像刚刚挖出来的坑一直在往左移动一样），直到遇到第一个比temp小的数，把temp放在这个数的右边

             v[j + ] = v[j];

             --j;

         }

         v[j + ] = temp;//安放temp

     }

 }

下面给出桶排序的最终代码

 void bucket_sort(vector<int>& v,int max){

     vector<vector<int>> bucket;

     bucket.resize();//默认有10个桶

     for (const int& n : v)

         bucket[putAt(n,max)].push_back(n);//将数放在对应的桶里用putAt()方法确定对应的桶

     for (auto& n : bucket)

         insert_sort(n);//用插入排序排列每个桶里的元素

     int num = ;

     for (const auto& i : bucket)//加强for中要改变被遍历的容器，必须用&修饰变量

         for (const auto& j : i)

             v[num++] = j;//遍历桶中的数据，依次放回原容器中

 }

参考资料：《算法导论 中文版》（英文版第三版）（美）ThomasH.Cormen，CharlesE.Leiserson，RonaldL.Rivest，CliffordStein 著；王刚，邹恒明，殷建平，王宏志等译

相关文章