排序系列第 5 篇聚焦快速排序：平均 O(n log n)、原地、常数低，但需通过枢轴策略与尾递归优化来规避最坏 O(n^2) 与栈深问题。本文从 ACERS 角度给出理论到工程落地的全景。

目标读者

  • 想把快排写到“工程可用”水平的开发者。
  • 对枢轴选择、重复元素处理、尾递归/混合策略有疑问的同学。
  • 需要理解 std::sort / Introsort 设计动机的人。

背景/动机

  • 快排因原地、缓存友好、常数低而常为首选，但最坏 O(n^2) 与重复元素性能需谨慎。
  • 工程实践通过随机枢轴、三数取中、三路划分、尾递归和小分段插排来提升稳健性。

A — Algorithm（题目与算法）

主题：在保持原地、低常数的前提下，实现平均 O(n log n)、抗退化的快速排序。

基础示例 数组 [3, 5, 2, 2, 8]，枢轴=3：

  • 分区后 → [2,2,3,5,8]，左侧小于 3，右侧大于等于 3。
  • 递归处理左右子数组。

C — Concepts（核心思想）

关键概念说明
枢轴选择随机枢轴、三数取中（首/中/尾取中）、五数取中等，减少退化概率。
分区策略Lomuto（单边）简单但交换多；Hoare（双边）交换少；三路划分适合重复多。
重复元素三路划分（<,=,>) 避免大量重复时退化。
尾递归优化始终递归较小段，对较大段用循环，控制栈深 O(log n)。
混合策略子数组小于阈值切换插排；递归深度过大切换堆排（Introsort 思想）。

复杂度

  • 平均时间 O(n log n)，最坏 O(n^2)（当枢轴极端不平衡）。
  • 空间：递归栈 O(log n) 平均，最坏 O(n)，可用尾递归优化减轻。
  • 不稳定，原地。

E — Engineering（工程应用）

场景 1：通用后端排序（Go）

背景：数据量 1e5，分布随机。 为何：Go 内置 sort.Slice 基于快排/堆排混合；演示改进版带小段插排。

package main
import "fmt"

func insertion(a []int, l, r int) {
    for i := l+1; i <= r; i++ {
        key := a[i]; j := i-1
        for j >= l && a[j] > key { a[j+1]=a[j]; j-- }
        a[j+1]=key
    }
}

func partition(a []int, l, r int) int {
    pivot := a[(l+r)>>1]
    i, j := l, r
    for i <= j {
        for a[i] < pivot { i++ }
        for a[j] > pivot { j-- }
        if i <= j { a[i], a[j] = a[j], a[i]; i++; j-- }
    }
    return i
}

func quick(a []int, l, r int) {
    for r-l+1 > 16 {
        p := partition(a, l, r)
        if p-l < r-p { quick(a, l, p-1); l = p } else { quick(a, p, r); r = p-1 }
    }
    insertion(a, l, r)
}

func main(){
    arr := []int{3,5,2,2,8,1,7}
    quick(arr,0,len(arr)-1)
    fmt.Println(arr)
}

场景 2：重复元素多的数组（Python 三路划分）

背景：大量重复值（如分桶后 ID 排序），二路分区容易退化。 为何：三路划分一次性处理 = pivot 的区间。

def quick3(a, l=0, r=None):
    if r is None: r = len(a)-1
    while l < r:
        if r - l + 1 <= 16:
            for i in range(l+1, r+1):
                key=a[i]; j=i-1
                while j>=l and a[j]>key:
                    a[j+1]=a[j]; j-=1
                a[j+1]=key
            return
        pivot = a[(l+r)//2]
        lt, i, gt = l, l, r
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]; lt+=1; i+=1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]; gt-=1
            else:
                i+=1
        if lt-l < r-gt: quick3(a, l, lt-1); l = gt+1
        else: quick3(a, gt+1, r); r = lt-1
    return a

arr=[3,5,2,2,8,1,7,2,2]
quick3(arr)
print(arr)

场景 3：C++ 性能敏感分区（Hoare + 三数取中）

背景：性能敏感、需低交换、枢轴更稳健。

#include <bits/stdc++.h>
using namespace std;

int median3(vector<int>& a, int l, int r){
    int m = l + (r-l)/2;
    if(a[m] < a[l]) swap(a[m], a[l]);
    if(a[r] < a[l]) swap(a[r], a[l]);
    if(a[m] < a[r]) swap(a[m], a[r]); // a[r] = median
    return a[r];
}

int partition(vector<int>& a, int l, int r){
    int pivot = median3(a,l,r);
    int i=l-1, j=r;
    while(true){
        do{ i++; } while(a[i] < pivot);
        do{ j--; } while(a[j] > pivot);
        if(i>=j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

void quick(vector<int>& a, int l, int r){
    while(l < r){
        if(r-l+1 <= 16){
            for(int i=l+1;i<=r;++i){int key=a[i], j=i-1; while(j>=l && a[j]>key){a[j+1]=a[j]; j--;} a[j+1]=key;}
            return;
        }
        int p = partition(a,l,r);
        if(p-l < r-p){ quick(a,l,p-1); l=p+1; }
        else{ quick(a,p+1,r); r=p-1; }
    }
}

场景 4：JavaScript 前端小数组优化

背景：中小数组排序，使用三数取中 + 插排阈值。

function insertion(a,l,r){
  for(let i=l+1;i<=r;i++){
    const key=a[i]; let j=i-1;
    while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
function partition(a,l,r){
  const m = l + ((r-l)>>1);
  if(a[m]<a[l]) [a[m],a[l]]=[a[l],a[m]];
  if(a[r]<a[l]) [a[r],a[l]]=[a[l],a[r]];
  if(a[r]<a[m]) [a[r],a[m]]=[a[m],a[r]];
  const pivot = a[r];
  let i=l-1;
  for(let j=l;j<r;j++) if(a[j]<=pivot){ i++; [a[i],a[j]]=[a[j],a[i]]; }
  [a[i+1],a[r]]=[a[r],a[i+1]];
  return i+1;
}
function quick(a,l=0,r=a.length-1){
  while(l<r){
    if(r-l+1<=16){ insertion(a,l,r); return; }
    const p=partition(a,l,r);
    if(p-l < r-p){ quick(a,l,p-1); l=p+1; }
    else{ quick(a,p+1,r); r=p-1; }
  }
  return a;
}
console.log(quick([3,5,2,2,8,1,7]));

R — Reflection（反思与深入）

  • 复杂度：平均 O(n log n)，最坏 O(n^2)；空间为栈深 O(log n) 平均，尾递归 + 小段插排可控。
  • 替代方案：
    • 需稳定或可预测上界 → 归并 / 堆排序 / TimSort。
    • 范围可知 → 计数/桶/基数。
    • 标准库选择：C++ std::sort = Introsort（快排+堆排+插排）；Python/Java 则是 TimSort（稳定）。
  • 为何当前方法可行：
    • 随机/三数取中降低退化概率；
    • 三路划分解决重复元素；
    • 尾递归 + 小段插排降低栈深与常数，贴合工程实践。

S — Summary（总结）

  • 快排优势：原地、常数低、缓存友好，平均 O(n log n)。
  • 风险点：枢轴极端导致 O(n^2)；重复元素多时退化；不稳定。
  • 稳健策略：随机/三数取中枢轴，三路划分应对重复，小分段插排，尾递归控制栈，必要时引入 Introsort 思想。
  • 选型建议：稳定需求或外部排序用归并/TimSort；内存紧张且随机分布选快排/Introsort；重复多用三路划分。

实践指南 / 步骤

  • 选枢轴策略：默认随机或三数取中；性能敏感可加五数取中。
  • 重复多则用三路划分；否则二路分区即可。
  • 设置小分段阈值（如 16/24），切换插排；设栈深阈值，必要时回退堆排（Introsort）。
  • 准备测试集：随机、逆序、全相等、重复多、大数组，检验退化与稳定性风险。

常见问题与注意事项

  • Lomuto 分区交换多，Hoare 分区返回索引需注意递归区间。
  • 递归深度过深导致栈溢出：用尾递归优化或迭代写法。
  • 重复元素未处理好时会导致退化：三路划分是关键。
  • 枢轴选择固定取首元素在有序数组上会退化。

可运行示例：多语言最小版

Python（随机枢轴 + 三路）

import random

def quick3(a, l=0, r=None):
    if r is None: r = len(a)-1
    while l < r:
        if r-l+1 <= 16:
            for i in range(l+1, r+1):
                key=a[i]; j=i-1
                while j>=l and a[j]>key:
                    a[j+1]=a[j]; j-=1
                a[j+1]=key
            return a
        pivot_i = random.randint(l, r)
        a[l], a[pivot_i] = a[pivot_i], a[l]
        pivot = a[l]
        lt, i, gt = l, l+1, r
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]; lt+=1; i+=1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]; gt-=1
            else:
                i+=1
        if lt-l < r-gt: quick3(a, l, lt-1); l = gt+1
        else: quick3(a, gt+1, r); r = lt-1
    return a

arr=[3,5,2,2,8,1,7,2,2]
quick3(arr); print(arr)

C（Hoare 分区 + 插排阈值）

#include <stdlib.h>
void insertion(int *a,int l,int r){
    for(int i=l+1;i<=r;i++){
        int key=a[i], j=i-1;
        while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
        a[j+1]=key;
    }
}
int partition(int *a,int l,int r){
    int pivot=a[(l+r)/2];
    int i=l-1, j=r+1;
    while(1){
        do{ i++; } while(a[i]<pivot);
        do{ j--; } while(a[j]>pivot);
        if(i>=j) return j;
        int t=a[i]; a[i]=a[j]; a[j]=t;
    }
}
void quick(int *a,int l,int r){
    while(l<r){
        if(r-l+1<=16){ insertion(a,l,r); return; }
        int p=partition(a,l,r);
        if(p-l < r-p){ quick(a,l,p); l=p+1; }
        else{ quick(a,p+1,r); r=p; }
    }
}

C++（三数取中 + Hoare）

int partition(vector<int>& a,int l,int r){
    int m=l+(r-l)/2;
    if(a[m]<a[l]) swap(a[m],a[l]);
    if(a[r]<a[l]) swap(a[r],a[l]);
    if(a[r]<a[m]) swap(a[r],a[m]);
    int pivot=a[m];
    int i=l-1,j=r+1;
    while(true){
        do{i++;}while(a[i]<pivot);
        do{j--;}while(a[j]>pivot);
        if(i>=j) return j;
        swap(a[i],a[j]);
    }
}

Go（简版二路）

func Quick(a []int, l, r int){
    for l<r {
        if r-l+1 <= 16 { insertion(a,l,r); return }
        p := partition(a,l,r)
        if p-l < r-p { Quick(a,l,p-1); l=p }
        else { Quick(a,p,r); r=p-1 }
    }
}

Rust（三路）

pub fn quick3(a: &mut [i32]) {
    fn insertion(a: &mut [i32]) {
        for i in 1..a.len() {
            let key=a[i]; let mut j=i as i32-1;
            while j>=0 && a[j as usize]>key { a[(j+1) as usize]=a[j as usize]; j-=1; }
            a[(j+1) as usize]=key;
        }
    }
    fn sort(a: &mut [i32]) {
        let n=a.len();
        if n<=16 { insertion(a); return; }
        let pivot=a[n/2];
        let (mut lt, mut i, mut gt) = (0,0,n-1);
        while i<=gt {
            if a[i]<pivot { a.swap(lt,i); lt+=1; i+=1; }
            else if a[i]>pivot { a.swap(i,gt); if gt==0 {break;} gt-=1; }
            else { i+=1; }
        }
        sort(&mut a[..lt]);
        sort(&mut a[gt+1..]);
    }
    if !a.is_empty() { sort(a); }
}

JavaScript（三数取中 + 插排）

function insertion(a,l,r){
  for(let i=l+1;i<=r;i++){
    const key=a[i]; let j=i-1;
    while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
function quick(a,l=0,r=a.length-1){
  while(l<r){
    if(r-l+1<=16){ insertion(a,l,r); return a; }
    const m=l+((r-l)>>1);
    if(a[m]<a[l]) [a[m],a[l]]=[a[l],a[m]];
    if(a[r]<a[l]) [a[r],a[l]]=[a[l],a[r]];
    if(a[r]<a[m]) [a[r],a[m]]=[a[m],a[r]];
    const pivot=a[m];
    let i=l, j=r;
    while(i<=j){
      while(a[i]<pivot) i++;
      while(a[j]>pivot) j--;
      if(i<=j){ [a[i],a[j]]=[a[j],a[i]]; i++; j--; }
    }
    if(j-l < r-i){ quick(a,l,j); l=i; }
    else { quick(a,i,r); r=j; }
  }
  return a;
}
console.log(quick([3,5,2,2,8,1,7]));

最佳实践与建议

  • 默认使用语言标准库排序；自实现需：随机/三数取中枢轴、三路划分（重复多）、小分段插排、尾递归控制栈。
  • 需要稳定时改用归并/TimSort；需要严格上界时考虑 Introsort（快排+堆排）。
  • 基准测试覆盖：随机、逆序、全相等、重复多、大规模，观察退化与常数。

小结 / 结论

  • 快排以原地、低常数著称，但必须用枢轴策略与三路划分避免退化。
  • 尾递归优化 + 插排阈值是工程实现的标配；深度过大可回退堆排（Introsort）。
  • 选型遵循：稳定/外部排序 → 归并/TimSort；内存紧张且随机分布 → 快排/Introsort；重复多 → 三路划分。

参考与延伸阅读

  • Hoare, “Quicksort” (1961)
  • Bentley & McIlroy, “Engineering a Sort Function” (1993)
  • C++ std::sort 与 std::stable_sort 源码笔记

元信息

  • 阅读时长：约 16 分钟
  • SEO 关键词：快速排序, 枢轴选择, 三路划分, 尾递归优化, Introsort
  • 元描述：排序专题第五篇，深入讲解快速排序的枢轴策略、三路划分、尾递归与混合优化，附多语言实现与工程选型建议。

行动号召（CTA）

  • 用真实数据分布基准测试：随机、逆序、重复多，比较随机枢轴 vs 固定枢轴性能。
  • 在你的排序实现中加入“小分段插排 + 尾递归优化”，对比栈深与耗时。
  • 关注后续系列：堆排序、非比较排序、TimSort/Introsort、排序选型实战篇。