C++快速排序（遞迴）演算法詳解

快速排序是由 C.A.R.Hoare 於 1962 年發明的遞迴排序演算法。它非常高效，通常用於對儲存在陣列中的專案列表進行排序。

快速排序通常寫成一個包含 3 個形參的遞回函數，這 3 個形參可以定義要排序的陣列的一部分，它們分別是，一個包含專案列表的陣列 arr，以及兩個下標 start 和 end，表示要排序的 arr 陣列段的開始和結束。可以將這 3 個形參寫作 arr[start .. end]。要對整個陣列進行排序，可以呼叫快速排序，將 start 設定為 0，並將 end 設定為陣列大小減 1。

快速排序的工作原理如下，如果 start 大於或等於 end，那麼被排序的 arr 段最多有一個元素，因此已經排序，在這種情況下，快速排序立即返回。否則，快速排序將通過選擇 arr[start .. end] 中的一個元素作為一個基準元素，來對 arr[start .. end] 進行分割區，然後重新排列 arr[start .. end]，以便所有小於基準的條目都在基準的左側，所有大於或等於基準的條目都在基準的右側。

實際上，分割區步驟重新排列了 arr[start..end]，以使它由子列表 1、基準元素和子列表 2 組成，如圖 1 所示。

---