排序與搜尋
快速排序
快速排序是另一種了不起的分治排序，但它把工作放在遞迴之前而非之後。選一個元素作為基準（pivot），再把其餘元素分成兩組：比基準小的都放左邊，比基準大的都放右邊。這時基準就落在了它最終的、正確的位置上，接著你對左右兩組各自遞迴地做快速排序。當分區縮小到空，陣列就排好了——不需要合併步驟。
其核心是分區（partition），而它是透過在同一個陣列內交換元素來完成的，所以快速排序原地排序，遞迴只佔用 O(log n) 的堆疊空間。想像按身高把一群人排成一排，圍繞一個選定的「參照人」：把比他矮的都挪到左邊，比他高的都挪到右邊；這個參照人此後再也不用動了。
當每次基準都把陣列大致對半切，遞迴約有 log n 層深、每層 n 的工作量——平均時間 O(n log n)；而在實務中，快速排序的常數很小、原地交換對快取友善，使它成為最快的通用排序。危險來自壞基準：若你反覆選到最小或最大的元素（例如用樸素的「取第一個元素」當基準、又碰上已排好序的資料），分區會極度不平衡，於是滑向 O(n^2)。好的實作用隨機基準或三數取中來躲開這點。注意快速排序不穩定。
void quicksort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; ++j)
if (a[j] < pivot) std::swap(a[i++], a[j]); // partition
std::swap(a[i], a[hi]); // pivot to its place
quicksort(a, lo, i - 1);
quicksort(a, i + 1, hi);
}分區之後，基準已在它最終的位置；再對左右兩側遞迴。平均 O(n log n)，最壞 O(n^2)。
快速排序平均 O(n log n)，但最壞是 O(n^2)；合併排序則始終 O(n log n)。實務中快排在速度和記憶體（原地）上勝出，合併排序在最壞情況保證和穩定性上勝出。C++ 的 std::sort 用的是內省排序（introsort）——一種快排，當遞迴過深時切換到堆積排序，把最壞情況封頂在 O(n log n)。
又稱
另見