C++排序 小結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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