一、快速排序：递归与分治的完美结合

快速排序，说白了就是「选个老大，分两拨，各自再选老大」。这个算法我用了十几年，每次面试新人我都爱问这个——因为它太能体现一个人的递归思维了。

我记得刚入行那会儿，第一次手写快排，分区函数写得一塌糊涂，递归调用直接栈溢出。嗯，今天咱们就把这块硬骨头啃下来。

1.1 分治思想：大事化小，小事化了

分治（Divide and Conquer）其实不神秘。你想想看，生活中我们处理复杂问题，不也是先拆成小问题吗？

快速排序的分治三步走：

• 选基准（Pivot）：从数组中挑一个元素当「标杆」
• 分区（Partition）：比基准小的放左边，大的放右边
• 递归排序：对左右两个子数组重复上述过程

我在项目中遇到过最典型的场景：需要对百万级日志按时间排序。用快排，选中间元素做基准，分区后递归，几毫秒就搞定。如果用冒泡排序？嗯，那得等到下班。

1.2 选基准：看似简单，实则暗藏玄机

选基准的方法有很多，我列个表给你看：

选法	做法	优点	缺点
固定选第一个	arr[low]	实现简单	有序数组性能退化到O(n²)
固定选最后一个	arr[high]	同上	同上
随机选	rand() % (high-low+1) + low	避免最坏情况	随机数有开销
三数取中	取首、中、尾三个数的中位数	工程中最常用	多几次比较

我个人习惯用「三数取中」。为什么？因为随机选虽然理论上好，但在嵌入式系统里，rand() 函数可能很慢。我曾经在一个资源受限的项目里，就因为 rand() 调用太频繁，导致排序比预期慢了 3 倍。换成三数取中后，问题迎刃而解。

1.3 分区：快排的灵魂所在

分区函数是快排的核心。我见过很多新手，递归写对了，分区却写错了。这里我给出最经典的 Lomuto 分区方案：

// 分区函数：返回基准元素的最终位置
int partition(int arr[], int low, int high) {
    // 选最后一个元素作为基准
    int pivot = arr[high];
    // i 指向「小于基准区」的最后一个位置
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准
        if (arr[j] <= pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 把基准放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

这段代码里，i 指针始终指向「已处理的小于基准的元素」的末尾。j 指针遍历整个数组。说白了，就是一趟扫描，把小于等于基准的都换到左边去。

1.4 递归排序：把分区结果串起来

有了分区函数，递归排序就水到渠成了：

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 1. 分区，得到基准位置
        int pi = partition(arr, low, high);
        
        // 2. 递归排序左半部分
        quickSort(arr, low, pi - 1);
        
        // 3. 递归排序右半部分
        quickSort(arr, pi + 1, high);
    }
    // 递归终止条件：low >= high，说明只有一个元素或没有元素
}

你看，递归的代码往往很简洁。但简洁不代表简单。这里有个关键点：递归调用时，基准元素本身已经排好了，所以左右子数组都不包含它。

为什么会这样？因为分区函数已经把基准放到了「它最终应该在的位置」。左边都比它小，右边都比它大。所以递归时，我们只需要处理左右两侧。

1.5 完整代码与运行示例

把上面两段代码合在一起，就是一个完整的快速排序：

#include <stdio.h>

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

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);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

运行结果：

原始数组: 10 7 8 9 1 5 
排序后: 1 5 7 8 9 10

1.6 快排的递归过程可视化

为了让你更直观地理解递归过程，我画了一张图：

1.7 避坑指南：我踩过的那些坑

做快排这么多年，我总结了几条血泪教训：

• 递归深度问题：最坏情况下（比如数组已经有序），递归深度等于数组长度。对于大数组，这可能导致栈溢出。解决方案：用三数取中选基准，或者改用迭代实现。
• 分区边界条件：我曾经写过 quickSort(arr, low, pi) 而不是 quickSort(arr, low, pi - 1)，结果陷入了无限递归。记住：基准元素已经排好了，不要再处理它。
• 小数组优化：当子数组长度小于某个阈值（比如 10）时，改用插入排序。我在一个项目中这样优化后，整体性能提升了 15%。

1.8 复杂度分析

情况	时间复杂度	空间复杂度	说明
平均情况	O(n log n)	O(log n)	递归栈深度为 log n
最坏情况	O(n²)	O(n)	数组有序且选第一个做基准
最好情况	O(n log n)	O(log n)	每次基准都正好在中间

快速排序之所以叫「快速」，就是因为平均情况下它比其他 O(n log n) 排序算法（比如归并排序）更快。原因在于：快排的常数因子小，而且对缓存友好。

好了，快速排序的递归实现就讲到这里。记住三个关键词：选基准、分区、递归。把这三点吃透了，快排就没什么秘密了。