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

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

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

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

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

不行，當我們以最左端元素為基準數時，必須先“從右往左查找”再“從左往右查找”。這個結論有些反直覺，我們來剖析一下原因。

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

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

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

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

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

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

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

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

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

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