排序与查找
快速排序
快速排序是另一种了不起的分治排序，但它把工作放在递归之前而非之后。选一个元素作为基准（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)。
又称
另见