快速排序是一種常見且高效的排序演算法,由 C. A. R. Hoare 提出。它的核心概念是分治法:先選出一個基準值,再將資料分成小於基準與大於等於基準的兩群,最後對兩群分別排序。
第一步是選擇基準點,第二步是將較小的元素移到左側、較大的元素移到右側,第三步則對左右兩個子集合重複同樣流程,直到每個子集合只剩一個元素。
實作時可先檢查陣列長度,若小於等於一就直接回傳。接著取出基準點,建立左右兩個暫存陣列,遍历原陣列並依大小分派,最後以遞迴方式合併排序結果。