算法导论 — 8.2 计数排序

笔记

假设输入的$n$n个元素中的每一个都是在$0$0 ~ $k$k内的一个整数。$k$k表示了输入元素所处的范围。一般在$k$k远小于$n$n时，可以采用计数排序算法。
　　计数排序的基本思想是：对每一个输入元素$x$x，确定小于$x$x的元素个数。利用这一信息，可以直接把$x$x放到正确的位置。例如，如果有$17$17个元素小于$x$x，则x就应该放在第$18$18个位置上。
　　以下为计数排序的伪代码。假设输入数组为$A[1..n]$A[1..n]，输出数组为$B[1..n]$B[1..n]，另外还有一个数组$C[0..k]$C[0..k]提供临时存储空间。
　　
　　下图给出了一个例子，输入数组为$<2, 5, 3, 0, 2, 3, 0, 3>$<2,5,3,0,2,3,0,3>。
　　
　　在计数排序的伪代码中，第$2$2 ~ $3$3行的for循环所花时间为$Θ(k)$Θ(k)，第$4$4 ~ $5$5行的for循环所花时间为$Θ(n)$Θ(n)，第$7$7 ~ $8$8行的for循环所花时间为$Θ(k)$Θ(k)，第$10$10 ~ $12$12行的for循环所花时间为$Θ(n)$Θ(n)。这样，计数排序总的时间代价为$Θ(k+n)$Θ(k+n)。在实际应用中，一般在$k = O(n)$k=O(n)时才会应用计数排序，此时计数排序的运行时间为$Θ(n)$Θ(n)。
　　在8.1节，我们得到结论，比较排序的运行时间的下界为$Ω(n{\rm lg}n)$Ω(nlgn)。然而计数排序的运行时间是优于$Ω(n{\rm lg}n)$Ω(nlgn)的，因为它并不是一个比较排序算法。
　　计数排序还是一个稳定排序算法，这一玄机在于伪代码的第$10$10行，从后向前遍历输入数组$A[1..n]$A[1..n]。假如在$A[1..n]$A[1..n]存在一组数值相同的元素，位置靠后的元素先取出，它在输出数组中的位置也相对靠后；而位置靠前的元素后取出，它在输出数组中的位置也相对靠前。

练习

8.2-1 参照图8-2的方法，说明$COUNTING-SORT$COUNTING−SORT在数组$A = <6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2>$A=<6,0,2,0,1,3,4,6,1,3,2>上的操作过程。
　　解
　　
　　
8.2-2 试证明$COUNTING-SORT$COUNTING−SORT是稳定的。
　　略

8.2-3 假设我们在$COUNTING-SORT$COUNTING−SORT的第10行循环的开始部分，将代码改写为：
　　
　　试证明该算法仍然是正确的。它还稳定吗?
　　略

8.2-4 设计一个算法，它能够对于任何给定的介于$0$0到$k$k之间的$n$n个整数先进行预处理，然后在$O(1)$O(1)时间内回答输入的$n$n个整数中有多少个落在区间$[a..b]$[a..b]内。你设计的算法的预处理时间应为$Θ(n+k)$Θ(n+k)。
　　解
　　以下直接给出伪代码。
　　

本节相关代码链接：
　　https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter08/Section_8.2