auto_ai 知识库

Appearance

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，通过"哨兵划分"将数组分为两部分，递归排序子数组。平均时间复杂度 O(n log n)，是实际应用中最常用的排序算法之一。

定义与核心原理 ​

快速排序的核心是哨兵划分（Partition）：选择一个基准元素（pivot），将数组中小于 pivot 的元素移到左边，大于 pivot 的移到右边，然后对左右子数组递归执行相同操作。

分治三步 ​

  1. 分解：选择基准元素，将数组划分为左右两部分
  2. 解决：递归排序左右子数组
  3. 合并：子数组有序后，整个数组自然有序（无需额外合并操作）

操作步骤 ​

以数组 [2, 4, 1, 0, 3, 5] 为例：

初始：[2, 4, 1, 0, 3, 5]
  ↓ 选择 2 为基准，哨兵划分
[1, 0, 2, 4, 3, 5]   ← 2 已就位
  ↓ 递归左子数组 [1, 0]    递归右子数组 [4, 3, 5]
[0, 1] 2 [3, 4, 5]
  ↓ 子数组长度为 1，终止递归
[0, 1, 2, 3, 4, 5]   ← 排序完成

哨兵划分的具体实现 ​

cpp
int partition(vector<int>& nums, int left, int right) {
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) j--;
        while (i < j && nums[i] <= nums[left]) i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[left]);
    return i;
}

复杂度分析 ​

情况时间复杂度说明
平均O(n log n)基准选择适中，递归树平衡
最好O(n log n)每次划分均匀
最坏O(n²)数组已有序且选首元素为基准
空间O(log n)递归栈深度

实践应用 ​

  • 通用排序：大多数编程语言的内置排序（如 C++ std::sort 底层为 introsort，结合快排和堆排）
  • Top K 问题：利用哨兵划分快速找到第 K 大元素（快速选择算法）
  • 数组去重：排序后相邻元素比较

常见误区 ​

  1. 基准选择不当导致退化：对已有序数组选首元素为基准 → O(n²)。优化：随机选择或三数取中
  2. 忘记处理重复元素：大量重复元素时，三路快排（< = > 三区）更高效
  3. 递归深度过大：最坏情况递归深度 n，可能栈溢出。优化：尾递归优化或改用迭代

一句话总结 ​

快排 = 哨兵划分 + 分治递归，平均 O(n log n)、空间 O(log n)；最坏 O(n²) 出现在数组已有序且固定取首元素为基准，随机化或三数取中可规避。

相关概念 ​