快速排序详解：分治策略与优化实现

2. 算法优化

虽然基本快速排序很快，但在输入数组已经有序或接近有序时，性能会退化为 O(n²)。实际工程中常采用以下两种优化策略。

三数取中法

选择第一个元素作为基准在有序数组下会导致分区极度不平衡。三数取中法通过选取左端、中间和右端三个元素的中值作为基准，能有效避免最坏情况。

int GetMidi(int* a, int left, int right) {
    int midi = (left + right) / 2;
    if (a[left] < a[midi]) {
        if (a[midi] < a[right]) {
            return midi;
        } else if (a[left] > a[right]) {
            return left;
        } else {
            return right;
        }
    } else {
        if (a[midi] > a[right]) {
            return midi;
        } else if (a[left] < a[right]) {
            return left;
        } else {
            return right;
        }
    }
}

小区间优化

当区间长度较小时，递归调用的开销可能超过排序本身的代价。此时切换为插入排序效率更高。通常认为区间长度小于 10 时进行优化。

if ((right - left + 1) < 10) {
    InsertSort(a + left, right - left + 1);
}

完整优化代码示例

#include <stdio.h>

void Swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 插入排序辅助函数
void InsertSort(int* a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

// 三数取中
int GetMidi(int* a, int left, int right) {
    int midi = (left + right) / 2;
    if (a[left] < a[midi]) {
        if (a[midi] < a[right]) return midi;
        else if (a[left] > a[right]) return left;
        else return right;
    } else {
        if (a[midi] > a[right]) return midi;
        else if (a[left] < a[right]) return left;
        else return right;
    }
}

// 优化后的快速排序
void QuickSort(int* a, int left, int right) {
    if (left >= right) return;

    // 小区间优化
    if ((right - left + 1) < 10) {
        InsertSort(a + left, right - left + 1);
        return;
    }

    // 三数取中
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);

    int keyi = left;
    int begin = left + 1;
    int end = right;

    while (begin <= end) {
        while (begin <= end && a[end] >= a[keyi]) end--;
        while (begin <= end && a[begin] <= a[keyi]) begin++;
        if (begin < end) Swap(&a[begin], &a[end]);
    }
    Swap(&a[keyi], &a[end]);

    QuickSort(a, left, end - 1);
    QuickSort(a, end + 1, right);
}

int main() {
    int arr[] = {2, 1, 3};
    QuickSort(arr, 0, 2);
    for (int i = 0; i < 3; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3. 前后指针法

这是另一种常见的快速排序实现，使用 prev 和 cur 两个指针遍历数组，将小于基准值的元素移动到前面。

排序过程

1. 定义 prev 指向 left，cur 指向 prev + 1。
2. cur 向右移动，若 a[cur] 小于基准值，则 prev 前进一步并交换 a[prev] 和 a[cur]。
3. 最后将基准值交换到 prev 位置。

int PartSort_TwoPointer(int* a, int left, int right) {
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);
    int keyi = left;
    int prev = left;
    int cur = prev + 1;

    while (cur <= right) {
        if (a[cur] < a[keyi] && ++prev != cur) {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    Swap(&a[prev], &a[keyi]);
    return prev;
}

void QuickSort_TwoPointer(int* a, int left, int right) {
    if (left >= right) return;
    int keyi = PartSort_TwoPointer(a, left, right);
    QuickSort_TwoPointer(a, left, keyi - 1);
    QuickSort_TwoPointer(a, keyi + 1, right);
}

4. 非递归实现（栈模拟）

递归实现简洁，但大规模数据可能导致栈溢出。非递归实现通过显式栈模拟递归过程，避免系统栈开销。

实现思路

1. 初始化栈，将初始左右下标入栈（注意顺序，先右后左）。
2. 循环取出栈顶的下标，进行分区操作。
3. 将分区后的左右子数组下标入栈，继续处理直到栈为空。

// 假设已实现栈结构 ST
void QuickSortNonR(int* a, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);

    while (!STEmpty(&st)) {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);

        int keyi = PartSort_TwoPointer(a, begin, end);

        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

复杂度分析

• 时间复杂度：平均 O(n log n)，最坏 O(n²)。
• 空间复杂度：最佳 O(log n)（递归栈深度），最坏 O(n)。

总结

快速排序凭借分治策略成为应用最广泛的排序算法之一。理解 Hoare 分区、前后指针法以及非递归实现的差异至关重要。在实际开发中，结合三数取中和小区间优化能有效规避极端数据带来的性能风险，确保算法在工程场景下的稳定性。