[算法导论读书笔记]线性时间排序——桶排序

桶排序的要求：

        当桶排序的输入符合均匀分布时，即可以以线性期望时间运行。与计数排序类似，桶排序也对输入做了某种假设，因此运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则假设输入由一个随机过程产生，该过程将元素均匀而独立地分布在某一区间。

基本思想：

        桶排序的思想就是把区间划分成n个相同大小的子区间，或称桶。然后将n个输入数分布到各个桶中去，因为输入数均匀而独立的分布在某一区间，所以，一般不会有很多数落在一个桶中。为了得到结果，先对桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

设计：

        在桶排序的算法的代码中，假设输入的是一个含有n个元素的数组A，且每个元素满足同一个范围，另外，还需要一个辅助数组B[0……n-1]来存放链表（桶），并解设可以用某种机制来维护这张表。

伪代码：

实现&&测试：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <unistd.h>
#include <sys/times.h>
using namespace std;
#define MAX 1000000
#define DEBUG

int main(int argc, char* argv[])
{
long beg, end;
struct tms begTms, endTms;
long clock_per_sec = sysconf(_SC_CLK_TCK);
int i;
int temp;
vector<int> T[100];

//vector<int> A(MAX) error, there A has have 1000000 elements, It's not our need
vector<int> A;
vector<int> C;
A.reserve(MAX);
C.reserve(MAX);
int B[MAX];

srand(time(0));
for( i = 0; i < MAX; i++)
{
temp = rand() % 100;
T[temp].push_back(temp);
B[i] = temp;
C.push_back(temp);
}

beg = times(&begTms);
for( i = 0;i < 100; i++)
{
//insert element into A in order
copy( T[i].begin(), T[i].end(), back_inserter(A));
}
//cout << "A.capacity() = " << A.capacity() << " A.size() = " << A.size() << endl;

end = times(&endTms);
printf("The time of bucket sort is :%ld ms\n", (end-beg) * 1000/ clock_per_sec);


beg = times(&begTms);
sort(B, B + MAX);
end = times(&endTms);
printf("The time of sort function in library(store data use array) is :%ld ms\n", (end-beg) * 1000/ clock_per_sec);

beg = times(&begTms);
sort(C.begin(), C.end());
end = times(&endTms);
printf("The time of sort function in library(store data use vector) is :%ld ms\n", (end-beg) * 1000/ clock_per_sec);

#ifdef DEBUG
for( i = 0; i < MAX/10; i += 10000)
{
printf("A[%d] = %d   B[%d] = %d    C[%d] = %d\n", i, A[i], i, B[i], i,C[i]);
}
#endif


return 0;
}

结论：

        时间比例基本与计数排序一样，比极度优化的库函数排序快了20倍左右。也就是说，计数排序和桶排序效率相差无几，具体应该使用那一个排序需要根据实际问题来选择。还有一点值得注意的是，虽然容器给我们操作数据提供了极大的方便，但同时效率也降低了很多，何时采用何种语言，也需要根据具体的情况进行选择。