🚀 快速排序算法详解

快速排序（Quick Sort）是计算机科学中经典的分治算法之一，以其高效性常用于大数据集的排序场景。其核心思想是通过基准值划分将数组分为两部分，再递归排序子数组。

🔍 原理解析

1. 选择基准值：从数组中选取一个元素作为基准（如中间值或首尾值）
2. 分区操作：将小于基准的元素移到左侧，大于基准的移到右侧
3. 递归处理：对左右子数组重复上述步骤，直到子数组长度为1

💡 分区过程可通过双指针技术实现，时间复杂度平均为 O(n log n)

📌 算法步骤

1. 若数组长度 ≤ 1，直接返回
2. 选取基准值 pivot（如 arr[0]）
3. 初始化左右指针 left 和 right
4. 循环交换直到 left ≥ right
   • 当 arr[left] < pivot 时 left++
   • 当 arr[right] > pivot 时 right--
5. 递归处理左右子数组

graph TD
    A[开始] --> B{数组长度是否≤1?}
    B -->|是| C[返回数组]
    B -->|否| D[选取基准值]
    D --> E[分区操作]
    E --> F[递归处理左右子数组]
    F --> G[合并结果]
    G --> H[排序完成]

📦 应用场景

• 大数据量排序（对比归并排序的内存消耗）
• 原地排序（空间复杂度 O(1)）
• 需要稳定排序时需注意实现细节

🌐 相关扩展

算法进阶课程 提供更多排序算法对比分析
数据结构基础 可帮助理解排序实现原理