快速排序¶

快速排序（quick sort）是一種基於分治策略的排序演算法，執行高效，應用廣泛。

快速排序的核心操作是“哨兵劃分”，其目標是：選擇陣列中的某個元素作為“基準數”，將所有小於基準數的元素移到其左側，而大於基準數的元素移到其右側。具體來說，哨兵劃分的流程如下圖所示。

選取陣列最左端元素作為基準數，初始化兩個指標 i 和 j 分別指向陣列的兩端。
設定一個迴圈，在每輪中使用 i（j）分別尋找第一個比基準數大（小）的元素，然後交換這兩個元素。
迴圈執行步驟 2. ，直到 i 和 j 相遇時停止，最後將基準數交換至兩個子陣列的分界線。

哨兵劃分完成後，原陣列被劃分成三部分：左子陣列、基準數、右子陣列，且滿足“左子陣列任意元素 \(\leq\) 基準數 \(\leq\) 右子陣列任意元素”。因此，我們接下來只需對這兩個子陣列進行排序。

快速排序的分治策略

哨兵劃分的實質是將一個較長陣列的排序問題簡化為兩個較短陣列的排序問題。

[file]{quick_sort}-[class]{quick_sort}-[func]{partition}

演算法流程¶

快速排序的整體流程如下圖所示。

首先，對原陣列執行一次“哨兵劃分”，得到未排序的左子陣列和右子陣列。
然後，對左子陣列和右子陣列分別遞迴執行“哨兵劃分”。
持續遞迴，直至子陣列長度為 1 時終止，從而完成整個陣列的排序。

[file]{quick_sort}-[class]{quick_sort}-[func]{quick_sort}

演算法特性¶

時間複雜度為 \(O(n \log n)\)、非自適應排序：在平均情況下，哨兵劃分的遞迴層數為 \(\log n\) ，每層中的總迴圈數為 \(n\) ，總體使用 \(O(n \log n)\) 時間。在最差情況下，每輪哨兵劃分操作都將長度為 \(n\) 的陣列劃分為長度為 \(0\) 和 \(n - 1\) 的兩個子陣列，此時遞迴層數達到 \(n\) ，每層中的迴圈數為 \(n\) ，總體使用 \(O(n^2)\) 時間。
空間複雜度為 \(O(n)\)、原地排序：在輸入陣列完全倒序的情況下，達到最差遞迴深度 \(n\) ，使用 \(O(n)\) 堆疊幀空間。排序操作是在原陣列上進行的，未藉助額外陣列。
非穩定排序：在哨兵劃分的最後一步，基準數可能會被交換至相等元素的右側。

快速排序為什麼快¶

從名稱上就能看出，快速排序在效率方面應該具有一定的優勢。儘管快速排序的平均時間複雜度與“合併排序”和“堆積排序”相同，但通常快速排序的效率更高，主要有以下原因。

出現最差情況的機率很低：雖然快速排序的最差時間複雜度為 \(O(n^2)\) ，沒有合併排序穩定，但在絕大多數情況下，快速排序能在 \(O(n \log n)\) 的時間複雜度下執行。
快取使用效率高：在執行哨兵劃分操作時，系統可將整個子陣列載入到快取，因此訪問元素的效率較高。而像“堆積排序”這類演算法需要跳躍式訪問元素，從而缺乏這一特性。
複雜度的常數係數小：在上述三種演算法中，快速排序的比較、賦值、交換等操作的總數量最少。這與“插入排序”比“泡沫排序”更快的原因類似。

基準數最佳化¶

快速排序在某些輸入下的時間效率可能降低。舉一個極端例子，假設輸入陣列是完全倒序的，由於我們選擇最左端元素作為基準數，那麼在哨兵劃分完成後，基準數被交換至陣列最右端，導致左子陣列長度為 \(n - 1\)、右子陣列長度為 \(0\) 。如此遞迴下去，每輪哨兵劃分後都有一個子陣列的長度為 \(0\) ，分治策略失效，快速排序退化為“泡沫排序”的近似形式。

為了儘量避免這種情況發生，我們可以最佳化哨兵劃分中的基準數的選取策略。例如，我們可以隨機選取一個元素作為基準數。然而，如果運氣不佳，每次都選到不理想的基準數，效率仍然不盡如人意。

需要注意的是，程式語言通常生成的是“偽隨機數”。如果我們針對偽隨機數序列構建一個特定的測試樣例，那麼快速排序的效率仍然可能劣化。

為了進一步改進，我們可以在陣列中選取三個候選元素（通常為陣列的首、尾、中點元素），並將這三個候選元素的中位數作為基準數。這樣一來，基準數“既不太小也不太大”的機率將大幅提升。當然，我們還可以選取更多候選元素，以進一步提高演算法的穩健性。採用這種方法後，時間複雜度劣化至 \(O(n^2)\) 的機率大大降低。

示例程式碼如下：

[file]{quick_sort}-[class]{quick_sort_median}-[func]{partition}

尾遞迴最佳化¶

在某些輸入下，快速排序可能佔用空間較多。以完全有序的輸入陣列為例，設遞迴中的子陣列長度為 \(m\) ，每輪哨兵劃分操作都將產生長度為 \(0\) 的左子陣列和長度為 \(m - 1\) 的右子陣列，這意味著每一層遞迴呼叫減少的問題規模非常小（只減少一個元素），遞迴樹的高度會達到 \(n - 1\) ，此時需要佔用 \(O(n)\) 大小的堆疊幀空間。

為了防止堆疊幀空間的累積，我們可以在每輪哨兵排序完成後，比較兩個子陣列的長度，僅對較短的子陣列進行遞迴。由於較短子陣列的長度不會超過 \(n / 2\) ，因此這種方法能確保遞迴深度不超過 \(\log n\) ，從而將最差空間複雜度最佳化至 \(O(\log n)\) 。程式碼如下所示：

[file]{quick_sort}-[class]{quick_sort_tail_call}-[func]{quick_sort}