HB1-快速排序¶

✅ 一、基础版快速排序（递归实现）¶

C
// 分区函数：选择第一个元素为基准，使用形参作为指针
int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选择第一个元素作为基准

    while (low < high) {
        // 从右向左找第一个小于基准的元素
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];  // 将小元素移到左边

        // 从左向右找第一个大于基准的元素
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];  // 将大元素移到右边
    }

    arr[low] = pivot;  // 将基准元素放到正确位置
    return low;        // 返回基准元素的最终位置
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 分区操作

        quickSort(arr, low, pi - 1);         // 递归排序左半部分
        quickSort(arr, pi + 1, high);        // 递归排序右半部分
    }
}

✅ 二、优化版：三路快排（处理重复元素）¶

当数组中存在大量重复元素时，标准快排性能下降（退化为 O(n²)），三路快排可有效优化。

C
// 三路快排：将数组分为 <pivot, ==pivot, >pivot 三部分
// 返回等于pivot区间的左右边界 [left, right]
void threeWayQuickSort(int arr[], int low, int high) {
    if (low >= high) return;

    int pivot = arr[low];
    int lt = low;      // arr[low...lt-1] < pivot
    int gt = high;     // arr[gt+1...high] > pivot
    int i = low + 1;   // 当前考察位置

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(&arr[i++], &arr[lt++]);
        } else if (arr[i] > pivot) {
            swap(&arr[i], &arr[gt--]);
        } else {
            i++;
        }
    }

    // 此时 [low, lt-1] < pivot, [lt, gt] == pivot, [gt+1, high] > pivot
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

✅ 优点：对重复元素多的数据性能极佳，平均时间复杂度仍为 O(n log n)，最坏情况更少。

✅ 三、非递归实现（使用栈模拟递归）¶

避免递归调用栈溢出，适用于大数组或栈空间受限环境。

C
#include <stdlib.h>

typedef struct {
    int low, high;
} StackNode;

void quickSortIterative(int arr[], int low, int high) {
    StackNode* stack = (StackNode*)malloc(sizeof(StackNode) * (high - low + 1));
    int top = -1;

    stack[++top] = (StackNode){low, high};

    while (top >= 0) {
        low = stack[top].low;
        high = stack[top--].high;

        if (low < high) {
            int pi = partition(arr, low, high);

            // 先压左区间，再压右区间（保证先处理左）
            stack[++top] = (StackNode){low, pi - 1};
            stack[++top] = (StackNode){pi + 1, high};
        }
    }

    free(stack);
}

⚠️ 注意：手动管理栈内存，需 free() 防止泄漏。

✅ 四、随机化快排（避免最坏情况）¶

选择随机基准，防止在已排序数组上退化为 O(n²)。

C
#include <stdlib.h>
#include <time.h>

// 随机化分区
int randomPartition(int arr[], int low, int high) {
    srand(time(NULL));  // 实际使用中应在主函数初始化一次
    int random = low + rand() % (high - low + 1);
    swap(&arr[random], &arr[high]);  // 将随机元素换到末尾
    return partition(arr, low, high);
}

void randomizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        randomizedQuickSort(arr, low, pi - 1);
        randomizedQuickSort(arr, pi + 1, high);
    }
}

✅ 建议：srand(time(NULL)) 应在 main() 中调用一次，避免多次调用导致随机性差。

✅ 算法核心思路总结¶

步骤	说明
1. 选择基准（pivot）	通常选首、尾、中位数或随机元素
2. 分区（Partition）	将小于/等于/大于 pivot 的元素分到不同区域
3. 递归处理左右子数组	对左右两部分分别快排

核心是 分治思想：Divide and Conquer。

✅ 时间复杂度分析¶

情况	时间复杂度	说明
最好情况	O(n log n)	每次分区都均分数组
平均情况	O(n log n)	数学期望下性能优秀
最坏情况	O(n²)	每次选到最大或最小元素作 pivot（如已排序数组）
空间复杂度	O(log n) ~ O(n)	递归栈深度，最好 O(log n)，最坏 O(n)

🔍 提示：通过 随机化 pivot 或 三数取中法 可极大降低最坏情况概率。

✅ 性能对比与其他排序比较¶

排序算法	平均时间	最坏时间	空间复杂度	是否稳定	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不稳定	通用、内存排序首选
归并排序	O(n log n)	O(n log n)	O(n)	✅ 稳定	外部排序、稳定需求
堆排序	O(n log n)	O(n log n)	O(1)	❌	内存受限、最坏性能要求高
插入排序	O(n²)	O(n²)	O(1)	✅	小数组、近有序

💡 快排是 实际应用中最常用的内部排序算法，C标准库 qsort() 即基于快排优化实现。

✅ 相关知识拓展¶

1. Hoare 与 Lomuto 分区方案¶

Lomuto：本文使用，代码简洁，但效率略低。
Hoare：原版快排分区，使用两个指针从两端向中间扫描，效率更高，但 pivot 不一定在最终位置。

C
// Hoare 分区示例
int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (1) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

2. 混合排序（Introsort）¶

现代C++ std::sort 使用 Introsort：结合快排、堆排序、插入排序。

快排主导；
递归深度超过阈值时切换为堆排序（防止 O(n²)）；
小数组（如 n < 16）用插入排序。

3. 原地排序 & 不稳定¶

快排是 原地排序（in-place），仅需少量额外空间。
不稳定：相等元素可能改变相对顺序。

✅ 应用场景¶

场景	是否适合快排	说明
内存中排序	✅ 强烈推荐	性能最优
外部排序（文件）	❌	推荐归并排序
要求稳定性	❌	改用归并或插入
实时系统（最坏性能敏感）	❌	改用堆排序或归并
大量重复元素	✅（用三路快排）	避免退化

✅ 变体汇总¶

变体	特点
随机快排	防止恶意输入导致退化
三路快排	优化重复元素场景
非递归快排	节省栈空间，防爆栈
三数取中法	pivot 选 `mid = (low+high)/2`，取 low, mid, high 的中位数
小数组插入排序优化	n < 10 时用插入排序提升常数性能

✅ 记忆口诀（背诵用）¶

一选基准，二做分区，三递归排左右。
随机 pivot 防退化，三路划分重元素。
非递归用栈模拟，小数组插排更优。

✅ 总结¶

快速排序是 理论与实践结合最成功的排序算法之一。虽然最坏时间复杂度为 O(n²)，但通过合理优化（随机化、三路划分、混合策略），在绝大多数场景下性能远超其他 O(n log n) 算法。

掌握以下几点即可应对面试与工程：

基础递归 + Lomuto 分区（必会）
三路快排（应对重复元素）
随机化 pivot（防最坏情况）
时间复杂度分析与对比