第八章 线性时间排序
8.4 桶排序
桶排序的思想就是把区间[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 <iostream> #include <list> using namespace std; struct Node { double value; Node *next; }; //桶排序主程序 void bucketSort(double* arr, int length) { Node key[10]; int number = 0; Node *p, *q;//插入节点临时变量 int counter = 0; for(int i = 0; i < 10; i++) { key[i].value = 0; key[i].next = NULL; } for(int i = 0; i < length; i++) { Node *insert = new Node(); insert->value = arr[i]; insert->next = NULL; number = arr[i] * 10; if(key[number].next == NULL) { key[number].next = insert; } else { p = &key[number]; q = key[number].next; while((q != NULL) && (q->value <= arr[i])) { q = q->next; p = p->next; } insert->next = q; p->next = insert; } } for(int i = 0; i < 10; i++) { p = key[i].next; if(p == NULL) continue; while(p != NULL) { arr[counter++] = p->value; p = p->next; } } } int main() { double a[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}; bucketSort(a, 10); for(int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; return 0; }
桶排序能够扩展为对整数元组序列进行排序,此时按照字典序排序。在面试的海量数据处理题目中,桶排序也很有作用。如对每天数以亿计的数据进行排序,直接排序即使采用nlgn的算法,依然是一件很恐怖的事情,内存也无法容纳如此多的数据。这时桶排序就可以有效地降低数据的数量级,再对降低了数量级的数据进行排序,可以得到比较良好的效果。