快速排序的 3 种 C 实现

快速排序是面试和竞赛中最常考的排序算法。本文对比 3 种经典实现：Lomuto 分区、Hoare 分区和三数取中优化版，分析各自的适用场景。

一、Lomuto 分区

思路简单：选择最后一个元素作为 pivot，将小于 pivot 的元素放到左边，大于的放到右边。

int lomuto_partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            i++;
        }
    }
    int tmp = arr[i]; arr[i] = arr[hi]; arr[hi] = tmp;
    return i;
}

void quicksort_lomuto(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = lomuto_partition(arr, lo, hi);
        quicksort_lomuto(arr, lo, p - 1);
        quicksort_lomuto(arr, p + 1, hi);
    }
}

二、Hoare 分区

双指针从两端向中间扫描，找到左侧大于 pivot 和右侧小于 pivot 的元素后交换。交换次数更少，分区更均衡。

int hoare_partition(int arr[], int lo, int hi) {
    int pivot = arr[(lo + hi) / 2];
    int i = lo - 1, j = hi + 1;
    while (1) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i >= j) return j;
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

void quicksort_hoare(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = hoare_partition(arr, lo, hi);
        quicksort_hoare(arr, lo, p);
        quicksort_hoare(arr, p + 1, hi);
    }
}

三、三数取中优化

对于已排序或接近排序的数据，固定选择 pivot 会导致最坏情况 O(n²)。三数取中法选择首、中、末三个元素的中位数作为 pivot，有效避免退化。

int median_of_three(int arr[], int lo, int hi) {
    int mid = (lo + hi) / 2;
    if (arr[lo] > arr[mid]) { int t = arr[lo]; arr[lo] = arr[mid]; arr[mid] = t; }
    if (arr[lo] > arr[hi])  { int t = arr[lo]; arr[lo] = arr[hi];  arr[hi]  = t; }
    if (arr[mid] > arr[hi]) { int t = arr[mid]; arr[mid] = arr[hi]; arr[hi] = t; }
    int t = arr[mid]; arr[mid] = arr[hi - 1]; arr[hi - 1] = t;
    return arr[hi - 1];
}

四、三种实现对比

• Lomuto：代码简单，适合教学；交换次数多，重复元素性能差
• Hoare：交换次数少约 3 倍；分区更均衡；递归深度更小
• 三数取中：避免已排序数据的最坏情况；实际运行中最稳定