算法数据结构C++实现5 - Bucket Sort 吊桶排序

吊桶排序的排序速度很快，平均是O(n)，能达到这么快的速度其中一个原因是它假设了输入值为范围是[0, 1)的小数。

Introduction to Algorithm这本书里面章8.4的算法，首先把原数组按照一定规律对照到每个吊桶（Bucket）里面，然后对每个Bucket排序，最后把这些Bucket串起来，就成为一个有序序列了。

下面是C++完整代码：

#include<iostream>  
#include<vector>  
#include<string>  
#include<list>  
#include<algorithm>  
  
using namespace std;  
  
template<typename C>  
void bucketSort(typename C& ca)     //难点  
{  
    int n = ca.size();  
    int k = 0, i = 0;  
    vector<list<double> > vld(n);       //难点  
  
    for(i=0; i<n; i++)  
    {  
        k = n * ca[i];  
        vld[k].push_back(ca[i]);  
    }  
  
    list<double> caTemp;  
    for(i = 0; i<n; i++)  
    {  
        if(!vld[i].empty())  
        {  
            vld[i].sort();  
            caTemp.merge(vld[i]);  
            //caTemp.insert(caTemp.end(),vld[i].begin(), vld[i].end());效果一样  
        }  
    }  
  
    i = 0;  
    for(auto x:caTemp)  
    {  
        ca[i] = x;  
        i++;  
    }  
}  
  
template<typename T>  
class Print  
{  
public:  
    Print(){}  
    void inline operator()(const T& x) const{cout<<x<<" ";}  
};//这就是函数对象，这里并没有带数据，只是一个简单的输出操作。  
  
void test()  
{  
    //初始化数组  
    double a[10] = {0.25, 0.38, 0.7, 0.45, 0.12, 0.78, 0.98,0.37, 0.83, 0.234};  
    vector<double> ld(a, a+10);     
  
    //排序前  
    for_each(ld.begin(), ld.end(), Print<double>());  
    cout<<endl;  
  
    //调用排序函数  
    bucketSort(ld);   
      
    //排序后  
    for(auto x:ld)  
        cout<<x<<" ";  
    cout<<endl;  
}  
  
int main()  
{  
    test();  
    return 0;  
}

总结：

C++是个非常好的开发工具，但是如果不熟悉的话，还是挺耗时间的。编程的时候一定要注意每一个细节，不然就可能被这些细节耽误很多时间。思维一定要保持高度逻辑性，否则就很难debug好。所谓差之毫厘谬以千里，有时候会被一个小；号，和&号搞的代码出错的，所以要非常注意。

补充：软件开发 , C++ ,