ACM基础（四）：排序之桶排序 Bucket Sort

一、思路

/* A：待排序数组。要求小数[0,1)，均匀分布（随机生成的）。B：已经创好的外存链表数组，共 n-1 个（是那种即使没有某些数，也会存在对应的链表的）。*/
BUCKET-SORT(A)n ← length[A]// 遍历数组A，将A中每个元素插入到链表B[? nA[i] ?]中for i ← 1 to ndo	insert A[i] into list B[? nA[i] ?]// 对每个链表B[i]进行插入排序for i ← 0 to n-1do	sort list B[i] with insertion sort将列表B[0],B[1],...,B[n-1]按序合并在一起

比如，B[0]的链表就是空的，但也提前分配好了。

二、时间复杂度

两部分：

• 除了对链表进行插入排序的步骤：$\Theta (n)$
• 对链表进行插入排序的步骤：插入排序的时间复杂度是$O(n^2)$，规模是$n_i$个（为了分析排序时间，假设$n_i$是一个随机变量，表示桶B[i]中放置的元素数量），结果就是n-1个链表所耗费插入排序的时间$\sum _{i=0}^{n?1}O(n_i^2)$。

所以，$T(n)=\Theta (n)+\sum _{i=0}^{n?1}O(n_i^2)$。