算法导论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\)位数，将每个数\(d_i\)视为三元组\((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)\)。