算法数据结构C++ - 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好。所谓差之毫厘谬以千里，有时候会被一个小；号，和&号搞的代码出错的，所以要非常注意。