算法导论 — 思考题8-2 线性时间原址排序

（线性时间原址排序）假设有一个包含$n$n个待排序数据记录的数组，且每条记录的关键字的值为$0$0或$1$1。对这样一组记录进行排序的算法可能具备如下三种特性中的一部分：
　　1. 算法的时间代价是$O(n)$O(n)。
　　2. 算法是稳定的。
　　3. 算法是原址排序，除了输入数组之外，算法只需要固定的额外存储空间。
　　a. 给出一个满足上述条件1和条件2的算法。
　　b. 给出一个满足上述条件1和条件3的算法。
　　c. 给出一个满足上述条件2和条件3的算法。
　　d. 你设计的算法$(a)$(a) ~ $(c)$(c)中的任一个是否可以用于$RADIX-SORT$RADIX−SORT的第$2$2行作为基础排序方法，从而使$RADIX-SORT$RADIX−SORT在排序有$b$b位关键字的$n$n条记录时的时间代价是$O(bn)$O(bn)？如果可以，请解释应如何处理；如果不行，请说明原因。
　　e. 假设有$n$n条记录，其中所有关键字的值都在$1$1到$k$k的区间内。你应该如何修改计数排序，使得它可以在$O(n+k)$O(n+k)时间内完成对$n$n条记录的原址排序。除输入数组外，你可以使用$O(k)$O(k)大小的额外存储空间。你给出的算法是稳定的吗？（提示：当$k = 3$k=3时，你应该如何做？）
　　
　　解
　　a.
　　计数排序。计数排序满足$O(n)$O(n)时间代价，并且是稳定的，但不是原址排序。
　　b.
　　快速排序。由于每条记录的关键字的值为$0$0或$1$1，所以快速排序经过一轮划分即可结束，一轮划分的时间开销为$O(n)$O(n)。另外快速排序是原址的，但不是稳定的。
　　c.
　　插入排序。插入排序是稳定的原址排序，但时间代价为$O(n^2)$O(n2)。
　　d.
　　由于$RADIX-SORT$RADIX−SORT所采用的基础排序方法必须是稳定的，并且要求每一轮排序具有$O(n)$O(n)时间代价，因此只有计数排序满足要求。
　　e.
　　回顾一些原址排序算法，比如插入排序、快速排序等，这些算法都是通过多次的元素两两交换来将所有元素放置在正确的位置上。如果计数排序要求是原址的，也只能通过交换的方式来将元素放置在正确的位置上。
　　计数排序的原理不再多赘述。我们用$A[1..n]$A[1..n]表示待排序数组，数组$C[1..k]$C[1..k]记录具有关键字$i (1$i(1~$k)$k)的元素应当所在的位置。假设处理到第$j$j个元素$A[j]$A[j]，那么$C[A[j]]$C[A[j]]表示该元素应当所在的位置。为简化表示，令$p = C[A[j]]$p=C[A[j]]。分$3$3种情况讨论：
　　(1) $p = j$p=j
　　此时$A[j]$A[j]就处于它应当所在的位置上，不用与其他元素交换，因此对$A[j]$A[j]不做任何处理，继续处理下一个元素。
　　(2) $p < j$p<j
　　此时按理说需要把$A[j]$A[j]和$A[p]$A[p]交换，把$A[j]$A[j]放置到它应当所在的位置上，但是这样做会有问题。计数排序是从后向前遍历来处理每一个元素。如果把$A[j]$A[j]交换到$A[p]$A[p]所在的位置，那么在接下来的遍历过程中，又会遇到到$A[j]$A[j]，这样一来$A[j]$A[j]这个元素会被重复处理。因此，在这种情况下，我们还是不做任何处理，跳过$A[j]$A[j]，继续处理下一个元素。
　　
　　(3) $p > j$p>j
　　此时将$A[j]$A[j]和$A[p]$A[p]交换，$A[j]$A[j]被交换到$A[p]$A[p]的位置上。由于$A[j]$A[j]是往靠后的位置交换，所以在接下来的遍历过程中，$A[j]$A[j]这个元素不会被重复处理。另外，$A[p]$A[p]被交换到了$A[j]$A[j]的位置上，那么交换后的$A[p]$A[p]该如何处理呢？这里先说明一点，如果$A[j]$A[j]应当放置在$A[p]$A[p]的位置上，那么说明交换前$A[p]$A[p]也没有处在正确的位置上，即$A[p]$A[p]是没有被处理过的。现在$A[p]$A[p]被交换到了$A[j]$A[j]的位置上，此时$A[p]$A[p]仍然有可能没有处在正确的位置上，故需要继续处理$A[p]$A[p]。对$A[p]$A[p]同样按照上述(1)(2)(3)分情况来处理。
　　
　　以上就是原址计数排序的流程。那么有一个问题，在第(2)种情况中跳过的那些元素，会被处理到吗？答案是会的。如果在第(2)种情况中跳过了一个元素$A[j]$A[j]，那么在接下来的遍历过程中，一定会遇到一个元素$A[k]$A[k] (其中$k < j$k<j)，该元素需要向后交换到$A[j]$A[j]的位置上。交换后，$A[j]$A[j]处于$A[k]$A[k]的位置上，这时$A[j]$A[j]会被继续处理。因此，即使在第(2)种情况中跳过了$A[j]$A[j]，$A[j]$A[j]也一定会在之后的过程中被处理到。
　　以下给出该算法的伪代码。
　　
　　
　　代码链接：
　　https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter08/Problem_8-2