算法导论8.3 Exercises 答案
8.3-1
$\begin{aligned}
\mathtt{COW} \ \mathtt{DOG} \ \mathtt{SEA} \ \mathtt{RUG} \ \mathtt{ROW} \ \mathtt{MOB} \ \mathtt{BOX} \ \mathtt{TAB} \ \mathtt{BAR} \ \mathtt{EAR} \ \mathtt{TAR} \ \mathtt{DIG} \ \mathtt{BIG} \ \mathtt{TEA} \ \mathtt{NOW} \ \mathtt{FOX} \
\end{aligned}\quad\rightarrow\quad
\begin{aligned}
\mathtt{SE\underline{A}} \ \mathtt{TE\underline{A}} \ \mathtt{MO\underline{B}} \ \mathtt{TA\underline{B}} \ \mathtt{RU\underline{G}} \ \mathtt{DO\underline{G}} \ \mathtt{DI\underline{G}} \ \mathtt{BI\underline{G}} \ \mathtt{BA\underline{R}} \ \mathtt{EA\underline{R}} \ \mathtt{TA\underline{R}} \ \mathtt{CO\underline{W}} \ \mathtt{RO\underline{W}} \ \mathtt{NO\underline{W}} \ \mathtt{BO\underline{X}} \ \mathtt{FO\underline{X}} \
\end{aligned}\quad\rightarrow\quad
\begin{aligned}
\mathtt{T\underline{A}B} \ \mathtt{B\underline{A}R} \ \mathtt{E\underline{A}R} \ \mathtt{T\underline{A}R} \ \mathtt{S\underline{E}A} \ \mathtt{T\underline{E}A} \ \mathtt{D\underline{I}G} \ \mathtt{B\underline{I}G} \ \mathtt{M\underline{O}B} \ \mathtt{D\underline{O}G} \ \mathtt{C\underline{O}W} \ \mathtt{R\underline{O}W} \ \mathtt{N\underline{O}W} \ \mathtt{B\underline{O}X} \ \mathtt{F\underline{O}X} \ \mathtt{R\underline{U}G} \
\end{aligned}\quad\rightarrow\quad
\begin{aligned}
\mathtt{\underline{B}AR} \ \mathtt{\underline{B}IG} \ \mathtt{\underline{B}OX} \ \mathtt{\underline{C}OW} \ \mathtt{\underline{D}IG} \ \mathtt{\underline{D}OG} \ \mathtt{\underline{E}AR} \ \mathtt{\underline{F}OX} \ \mathtt{\underline{M}OB} \ \mathtt{\underline{N}OW} \ \mathtt{\underline{R}OW} \ \mathtt{\underline{R}UG} \ \mathtt{\underline{S}EA} \ \mathtt{\underline{T}AB} \ \mathtt{\underline{T}AR} \ \mathtt{\underline{T}EA} \
\end{aligned}$
8.3-2
插入排序和归并排序是稳定的，堆排序和快速排序是不稳定的。
为了强迫这两种排序是稳定的，可以考虑将每一个数$A[i]$和它的下标$i$组合成为一个二元组$(A[i],i)$，然后再进行排序，这些二元组的比较规则是如果第$1$关键字不一样，那么以第$1$关键字比较结果为最终结果，否则以第$2$关键比较结果为最终结果（即字典序）。如对数组$\langle 2,2,3,1,1\rangle$就转化成了对二元组$\langle (2,1),(2,2),(3,3),(1,4),(1,5)\rangle$进行排序。由于第$2$关键字必定不一样（因为是下标），所以每一对二元组都是不一样的，从而保证了第$1$关键字的稳定性。
附加的代价：每一个元素都需要多一个值来代替，空间占用多了一倍；如果数值相同，那么还需要多进行一次比较，但是不考虑常数的情况下，时间复杂度仍然相同。
8.3-3
使用归纳法的证明过程如下。
假设第$i$次循环开始前，所有数已经按照第前$i-1$位完成排序，第$i$次循环完成后，所有数已经按照第前$i$位完成排序。
当$i=1$的循环进行前，已经按照$0$个关键字进行排序，原结论成立。
当$i>1$时，假设已经按照前$i-1$位完成排序，那么考虑第$i$位。如果两个数的第$i$位相同，那么由于这个调用的排序算法是一个稳定排序算法，那么它们的顺序仍然保持不变；如果两个数的第$i$位不同，那么这两个数按照这个数位进行排序。最终排序完成后，所有数已经按照第前$i$位完成排序。
因此，基数排序算法是正确的。
8.3-4
计数排序中，子程序计算$C$数组的部分可以离线$1$次完成，在这$1$次中，只需要计算$d$次即可，将$C$数组保存成一个$d\times b$（这里的$b$将会非常小）的表留给算法COUNTING-SORT的第11行for循环使用。
计算$C$数组只需要$1$次传递，算法COUNTING-SORT的第11行for循环使用了$d$次，一共仅需$d+1$次转递。
8.3-5
将每一个数视为一个$n$进制数。那么由于最大值仅有$n^3-1$，那么这些数在$n$进制下仅有$3$位数，将每个数$di$视为三元组$(d{i,2},d{i,1},d{i,0})$，再进行基数排序即可。
在这种情况下，基数排序的轮数为$3$次，如果子排序算法使用计数排序，那么每次调用计数排序的值域参数大小为$n$，而且这个数组的长度也为$n$。因此整个排序的时间复杂度为$O(n)$。
$\star$ 8.3-6
如果一共要给$n$个数排序，当所有数都不相同时，达到那么最坏情况。此时至少需要$n$轮的排序；如果这个算法机械地检查到最低位才返回（哪怕是只剩下一个数也不返回），那么可以达到$\Theta(10^d)$轮。递归达到最深时，最坏情况下每一位所有数的卡片都要保存一次，即$\Theta(dn)$。