快速排序

定义与基本思想

快速排序（Quick Sort）是一种分治法思想的高效排序算法。其基本思想是：每次选取一个“基准”元素，将序列分为两部分，左边都比基准小，右边都比基准大，然后递归地对两部分分别排序。

快速排序

点击“执行一步”观察算法状态变化。

算法描述

选取基准元素（如第一个元素）
将序列划分为两部分，左边小于基准，右边大于基准
分别对左右两部分递归进行快速排序

伪代码如下：

function quickSort(A, low, high):
    if low < high:
        pivot = partition(A, low, high)
        quickSort(A, low, pivot-1)
        quickSort(A, pivot+1, high)

function partition(A, low, high):
    pivot = A[low]
    i = low
    j = high
    while i < j:
        while i < j and A[j] >= pivot:
            j--
        A[i] = A[j]
        while i < j and A[i] <= pivot:
            i++
        A[j] = A[i]
    A[i] = pivot
    return i

代码实现

int Partition(int A[], int low, int high) {
    int pivot = A[low];        // 以第一个元素为基准
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];      // 小于基准的移到左边
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];      // 大于基准的移到右边
    }
    A[low] = pivot;            // 基准归位
    return low;                // 返回基准位置
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivot = Partition(A, low, high);
        QuickSort(A, low, pivot - 1);   // 左半部分
        QuickSort(A, pivot + 1, high);  // 右半部分
    }
}

基准元素选择的优化

随机选择：随机取一个元素作为基准，避免最坏情况
三数取中：取首、中、尾三个元素的中间值作为基准，降低退化为 $O(n^2)$ 的概率

时间复杂度分析

最好/平均情况： $O(n\log n)$
最坏情况： $O(n^2)$ （极端不平衡划分）
空间复杂度： $O(\log n)$ （递归栈）
稳定性：不稳定排序

习题

习题 1

对数组 $A = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]$ 进行快速排序，写出第一次划分后的结果。

参考答案

快速排序基准元素一次划分

解题思路：

本题考查快速排序的第一次划分。核心思想是选取一个基准元素，把序列划分为“比基准小”和“比基准大”的左右两个部分，划分结束后基准元素就位到其最终位置。

详细步骤：

以 6 为基准，左边比 6 小，右边比 6 大
一次划分后：[5, 1, 2, 3, 4, 6, 7, 9, 10, 8]（6 在中间）
校验：划分结果中 6 左侧的元素都小于 6，右侧的元素都大于 6，基准 6 落在下标 5 处。

最终答案：

如上，6 左边都小于 6，右边都大于 6。

习题 2

快速排序的时间复杂度和空间复杂度分别是多少？

参考答案

快速排序时间复杂度空间复杂度

解题思路：

本题考查快速排序的复杂度分析。快速排序的效率取决于基准选择与递归深度：平均情况下递归树深度为 $O(\log n)$ 、每层代价 $O(n)$ ，故平均时间复杂度为 $O(n \log n)$ ；若数据已有序导致划分极不均衡，最坏退化为 $O(n^2)$ 。

详细步骤：

时间复杂度 $O(n \log n)$ （平均）， $O(n^2)$ （最坏）
空间复杂度 $O(\log n)$ ：平均递归深度为 $O(\log n)$ ，最坏可达 $O(n)$ 。
对比参考：堆排序时间复杂度恒为 $O(n \log n)$ 、空间为 $O(1)$ ；归并排序时间复杂度恒为 $O(n \log n)$ 、空间为 $O(n)$ 。