计数排序

假设n个输入元素中每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为Θ(n)。

基本思想

对每个输入元素x，确定小于x的元素的个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了。例如，如果有17个元素小于x，则x就应该在第18个输出位置上。

伪代码

假设输入是一个数组A[1..n]，A.length=n。我们还需要两个数组: B[1..n]存放排序的输出，C[0..k]提供临时存储空间。

COUNTING-SORT(A, B, k)
let C[0..k] be a new array
for i = 0 to k
  C[i] = 0
for j = 1 to A.length
  C[A[j]] = C[A[j]] + 1
// C[i] now contains the number of elements equal to i.
for i = 1 to k
  C[i] = C[i] + C[i - 1]
// C[i] now contains the number of elements less than or equal to i.
for j = A.length downto 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] - 1

算法运行示例

算法运行的时间复杂度为Θ(n)。
计数排序是稳定的。

基数排序

为了确保基数排序的正确性，一位数排序算法必须是稳定的。

RADIX-SORT(A, d)
for i = 1 to d
  use a stable

对n个d位数来说，每一轮排序耗时Θ(n+k)。共有d轮，因此基数排序的总时间为&Theta(d(n+k))。

当d为常数且k=O(n)时，基数排序具有线性的时间代价。

桶排序

假设输入数据服从均匀分布，平均情况下它的时间代价为O(n)。与计数排序类似，因为对输入数据作了某种假设，桶排序的速度也很快。具体来说，计数排序假设输入数据都属于一个小区间内的整数，而桶排序则假设输入是由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间上。

桶排序将[0,1)区间划分为n个相同大小的子区间，或称为桶。然后，将n个输入数分别放到各个桶中。为了得到输出结果，我们先对每个桶中的数进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。

我们假设输入是一个包含n个元素的数组A，且每个元素A[i]满足0≤A[i]<1。此外，算法还需要一个临时数组B[0..n-1]来存放链表（即桶），并假设存在一种用于维护这些链表的机制。

BUCKET-SORT(A）
n = A.length
let B[0..n-1] be a new array
for i = 0 to n-1
  make B[i] an empty list
for i = 1 to n
  insert A[i] into list B[nA[i]]
for i = 0 to n - 1
  sort list B[i] with insertion sort
concatenate the lists B[0], B[1], ..., B[n-1] together in order

算法示例