举个来说明桶排序的过程，假设现在有A={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68}，桶排序如下所示：

     研究过计数排序我们知道了————计数排序是假设输入是由一个小范围内的整数构成，而桶排序则假设输入由一个随机过程产生的，该过程将元素均匀而独立地分布在区间[0，1)上。当桶排序的输入符合均匀分布时，即可以线性期望时间运行。桶排序的思想是：把区间[0，1)划分成n个相同大小的子区间，成为桶（bucket），然后将n个输入数分布到各个桶中去，对各个桶中的数进行排序，然后按照次序把各个桶中的元素列出来即可。

　　数中给出了桶排序的伪代码，假设输入是一个含有n个元素的数组A，且每个元素满足0≤A[i]<1，另外需要一个辅助数组B[0....n-1]来存放链表（桶）。伪代码如下所示：

BUCKET_SORT(A)
   n = length(A)
   for i= 1 to n
       do insert A[i] into list B
   for i=0 to n-1
       do sort list B[i] with insertion sort
   concatenate the list B[0]、B[1]，，，B[n-1] together in order

现在根据伪代码实现真正的桶排序，这里使用了c++的方法以及STL中的list以及迭代器的功能。以及在桶中使用了插入排序的算法的来对桶中元素进行排序。

<pre name="code" class="cpp">#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>
using namespace std;

void bucket_sort(float *datas, size_t length)
{
	int i, j;
	int index;
	float fvalue;
	size_t lsize;
	list<float> *retlist = new list<float>[length];
	list<float>::iterator iter;
	list<float>::iterator prioiter, enditer;

	for (i = 0; i<length; ++i)
	{
		index = static_cast<int>(datas[i] * 10);
		//insert a new element
		retlist[index].push_back(datas[i]);
		lsize = retlist[index].size();
		if (lsize > 1)
		{
			//get the last element in the list[index]
			iter = --retlist[index].end();
			fvalue = http://www.mamicode.com/*iter;>





算法导论------------桶排序算法之研究