本文转自 http://blog.csdn.net/heaven13483/article/details/7716829
桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间，每一个区间称为桶（bucket）。然后，将n个输入数据分布到各个桶中去。因为输入数均匀且独立均匀分布在[0, 1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各个桶中的元素列出来即可。
在桶排序算法中，假设输入的是一个含n个元素的数组A，且每个元素满足0≤A[i]<1。另外，还需要一个辅助数组B[0..n-1]来存放链表（桶），并假设可以用某种机制来维护这些表。
- BUCKET-SORT(A)
- 1 n ← length[A]
- 2 for i ← 1 to n
- 3 do insert A[i] into list B[⌊n A[i]⌋]
- 4 for i ← 0 to n - 1
- 5 do sort list B[i] with insertion sort
- 6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order
下图表示出了桶排序作用于有10个数的输入数组上的操作过程。
下面是实现的C++源代码，可直接复制运行。
- #include <time.h>
- #include <iostream>
- #include <iomanip>
- using namespace std;
- /*initial arr*/
- void InitialArr(double *arr,int n)
- {
- srand((unsigned)time(NULL));
- for (int i = 0; i<n;i++)
- {
- arr[i] = rand()/double(RAND_MAX+1); //(0.1)
- }
- }
- /* print arr*/
- void PrintArr(double *arr,int n)
- {
- for (int i = 0;i < n; i++)
- {
- cout<<setw(15)<<arr[i];
- if ((i+1)%5 == 0 || i == n-1)
- {
- cout<<endl;
- }
- }
- }
- void BucketSort(double * arr,int n)
- {
- double **bucket = new double*[10];
- for (int i = 0;i<10;i++)
- {
- bucket[i] = new double[n];
- }
- int count[10] = {0};
- for (int i = 0 ; i < n ; i++)
- {
- double temp = arr[i];
- int flag = (int)(arr[i]*10); //flag标识小树的第一位
- bucket[flag][count[flag]] = temp; //用二维数组的每个向量来存放小树第一位相同的数据
- int j = count[flag]++;
- /* 利用插入排序对每一行进行排序 */
- for(;j > 0 && temp < bucket[flag][j - 1]; --j)
- {
- bucket[flag][j] = bucket[flag][j-1];
- }
- bucket[flag][j] =temp;
- }
- /* 所有数据重新链接 */
- int k=0;
- for (int i = 0 ; i < 10 ; i++)
- {
- for (int j = 0 ; j< count[i];j++)
- {
- arr[k] = bucket[i][j];
- k++;
- }
- }
- for (int i = 0 ; i<10 ;i++)
- {
- delete bucket[i];
- bucket[i] =NULL;
- }
- delete []bucket;
- bucket = NULL;
- }
- void main()
- {
- double *arr=new double[10];
- InitialArr(arr, 10);
- BucketSort(arr, 10);
- PrintArr(arr,10);
- delete [] arr;
- }
而如果要使用结构体知识，和链接指印技术的话，可以使用下列代码，但现在的《算法导论》中还没有讲到数据结构，因为建议使用上面的。
- #include <iostream>
- 2 #include <list>
- 3
- 4 using namespace std;
- 5
- 6 struct Node
- 7 {
- 8 double value;
- 9 Node *next;
- 10 };
- 11 //桶排序主程序
- 12 void bucketSort(double* arr, int length)
- 13 {
- 14 Node key[10];
- 15 int number = 0;
- 16 Node *p, *q;//插入节点临时变量
- 17 int counter = 0;
- 18 for(int i = 0; i < 10; i++)
- 19 {
- 20 key[i].value = 0;
- 21 key[i].next = NULL;
- 22 }
- 23
- 24 for(int i = 0; i < length; i++)
- 25 {
- 26 Node *insert = new Node();
- 27 insert->value = arr[i];
- 28 insert->next = NULL;
- 29 number = arr[i] * 10;
- 30 if(key[number].next == NULL)
- 31 {
- 32 key[number].next = insert;
- 33 }
- 34 else
- 35 {
- 36 p = &key[number];
- 37 q = key[number].next;
- 38 while((q != NULL) && (q->value <= arr[i]))
- 39 {
- 40 q = q->next;
- 41 p = p->next;
- 42 }
- 43 insert->next = q;
- 44 p->next = insert;
- 45 }
- 46 }
- 47 for(int i = 0; i < 10; i++)
- 48 {
- 49 p = key[i].next;
- 50 if(p == NULL)
- 51 continue;
- 52 while(p != NULL)
- 53 {
- 54 arr[counter++] = p->value;
- 55 p = p->next;
- 56 }
- 57 }
- 58 }
- 59
- 60 int main()
- 61 {
- 62 double a[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
- 63 bucketSort(a, 10);
- 64 for(int i = 0; i < 10; i++)
- 65 {
- 66 cout << a[i] << " ";
- 67 }
- 68 cout << endl;
- 69 return 0;
- 70 }
桶排序能够扩展为对整数元组序列进行排序，此时按照字典序排序。在面试的海量数据处理题目中，桶排序也很有作用。如对每天数以亿计的数据进行排序，直接排序即使采用nlgn的算法，依然是一件很恐怖的事情，内存也无法容纳如此多的数据。这时桶排序就可以有效地降低数据的数量级，再对降低了数量级的数据进行排序，可以得到比较良好的效果。