C++排序 小結(jié)

排序算法穩(wěn)定性在什么情況下是必須的？

在現(xiàn)實中，我們有可能是在對象的某個屬性上進行排序。例如，學(xué)生有姓名和身高兩個屬性，我們希望實現(xiàn)一個多級排序/

先按照姓名進行排序，得到 (A, 180) (B, 185) (C, 170) (D, 170) ；接下來對身高進行排序。由于排序算法不穩(wěn)定，我們可能得到 (D, 170) (C, 170) (A, 180) (B, 185) 。

可以發(fā)現(xiàn)，學(xué)生 D 和 C 的位置發(fā)生了交換，姓名的有序性被破壞了，而這是我們不希望看到的。

哨兵劃分中“從右往左查找”與“從左往右查找”的順序可以交換嗎？

不行，當(dāng)我們以最左端元素為基準(zhǔn)數(shù)時，必須先“從右往左查找”再“從左往右查找”。這個結(jié)論有些反直覺，我們來剖析一下原因。

哨兵劃分 partition() 的最后一步是交換 nums[left] 和 nums[i] 。完成交換后，基準(zhǔn)數(shù)左邊的元素都 <= 基準(zhǔn)數(shù)，這就要求最后一步交換前 nums[left] >= nums[i] 必須成立。假設(shè)我們先“從左往右查找”，那么如果找不到比基準(zhǔn)數(shù)更小的元素，則會在 i == j 時跳出循環(huán)，此時可能 nums[j] == nums[i] > nums[left]。也就是說，此時最后一步交換操作會把一個比基準(zhǔn)數(shù)更大的元素交換至數(shù)組最左端，導(dǎo)致哨兵劃分失敗。

舉個例子，給定數(shù)組 [0, 0, 0, 0, 1] ，如果先“從左向右查找”，哨兵劃分后數(shù)組為 [1, 0, 0, 0, 0] ，這個結(jié)果是不正確的。

再深入思考一下，如果我們選擇 nums[right] 為基準(zhǔn)數(shù)，那么正好反過來，必須先“從左往右查找”。

關(guān)于尾遞歸優(yōu)化，為什么選短的數(shù)組能保證遞歸深度不超過 $\log ?n$ ？

遞歸深度就是當(dāng)前未返回的遞歸方法的數(shù)量。每輪哨兵劃分我們將原數(shù)組劃分為兩個子數(shù)組。在尾遞歸優(yōu)化后，向下遞歸的子數(shù)組長度最大為原數(shù)組的一半長度。假設(shè)最差情況，一直為一半長度，那么最終的遞歸深度就是 $\log ?n$ 。

回顧原始的快速排序，我們有可能會連續(xù)地遞歸長度較大的數(shù)組，最差情況下為 $n$、 $n?1$ 、$\dots$、 $2$ 、$1$ ，遞歸深度為 $n$ 。尾遞歸優(yōu)化可以避免這種情況的出現(xiàn)。

當(dāng)數(shù)組中所有元素都相等時，快速排序的時間復(fù)雜度是 $O(n^2)$ 嗎？該如何處理這種退化情況？

是的。這種情況可以考慮通過哨兵劃分將數(shù)組劃分為三個部分：小于、等于、大于基準(zhǔn)數(shù)。僅向下遞歸小于和大于的兩部分。在該方法下，輸入元素全部相等的數(shù)組，僅一輪哨兵劃分即可完成排序。

桶排序的最差時間復(fù)雜度為什么是 $O(n^2)$ ？

最差情況下，所有元素被分至同一個桶中。如果我們采用一個 $O(n^2)$ 算法來排序這些元素，則時間復(fù)雜度為 $O(n^2)$ 。