快速排序 快速排序是一种基于分治策略的高效排序算法，其核心思想是选取一个基准元素，将待排序序列划分为左右两个子序列，使得左边序列的所有元素都小于等于基准，右边序列的所有元素都大于等于基准，然后对这两个子序列递归地进行相同操作，直到整个序列有序。 详细步骤分解 基本思想与选择基准 首先，从待排序的数组（或子数组）中选择一个元素作为“基准”。基准的选择有多种方式，例如总是选择第一个元素、最后一个元素、中间的元素，或者随机选择一个元素。为了讲解方便，我们通常选择第一个元素作为基准。假设我们有一个数组 arr ，其左右边界索引分别为 left 和 right （初始时 left = 0 , right = arr.length - 1 ）。我们选择 pivot = arr[left] 作为基准。 分区操作 - 核心步骤 分区是快速排序算法的核心。目标是重新排列数组，使得所有小于等于基准的元素都位于基准的左边，所有大于基准的元素都位于基准的右边。基准元素本身则被放置在其最终的正确位置上。这个最终位置的索引被称为分区点。我们使用双指针法（以 Hoare 分区方案为例）来实现这一过程： 步骤 2.1：初始化指针 。设置两个指针 i 和 j 。 i 从序列的最左端（ left ）开始向右扫描，寻找大于基准的元素； j 从序列的最右端（ right ）开始向左扫描，寻找小于等于基准的元素。 步骤 2.2：扫描与交换 。 首先，让指针 j 从右向左移动，直到找到第一个小于或等于基准值 pivot 的元素。 然后，让指针 i 从左向右移动，直到找到第一个大于基准值 pivot 的元素。 如果此时 i 仍然小于 j （即两个指针尚未相遇或交叉），则交换 arr[i] 和 arr[j] 的值。这一步将一个大的元素（在左边）和一个小的元素（在右边）进行了交换，使它们更接近正确的一侧。 步骤 2.3：重复扫描 。重复步骤 2.2（先移动 j ，再移动 i ，然后检查并交换），直到指针 i 和 j 相遇或交叉（即 i >= j ）。此时，扫描停止。 步骤 2.4：放置基准 。当 i 和 j 相遇后，我们需要将基准元素放到其最终的正确位置。请注意，在 Hoare 分区方案中，相遇点（ j 指针的位置）通常保证了其左边的元素都小于等于基准。因此，我们将基准元素 arr[left] 与 arr[j] 进行交换。交换后，基准元素 pivot 就位于索引 j 处。此时，数组被分成了三个部分： arr[left...j-1] ：所有元素 <= pivot arr[j] ：基准元素，已经在其排序后的正确位置上。 arr[j+1...right] ：所有元素 > pivot 递归排序 现在，基准元素已经位于其最终位置。接下来，我们递归地将相同的算法应用于基准左边和右边的两个子数组。 对左子数组 arr[left...j-1] 递归执行快速排序。 对右子数组 arr[j+1...right] 递归执行快速排序。 递归终止条件 ：当一个子数组的长度为 0 或 1 时（即 left >= right ），它自然就是有序的，无需继续递归。 完整示例 对数组 [5, 2, 9, 1, 5, 6] 进行升序排序。 初始状态 : [5, 2, 9, 1, 5, 6] , left=0 , right=5 , pivot=5 (第一个元素)。 第一轮分区 : j 从右向左找 <=5 的数，找到 6 (索引5)大于5，继续，找到 5 (索引4) <=5， j 停在4。 i 从左向右找 >5 的数， 2 (索引1)不大于5，继续， 9 (索引2) >5， i 停在2。 i(2) < j(4) ，交换 9 和 5 ：数组变为 [5, 2, 5, 1, 9, 6] 。 继续， j 从4向左， 9 >5，继续， 1 (索引3)<=5， j 停在3。 i 从2向右， 5 不大于5，继续， i 移动到3。 此时 i(3) >= j(3) ，扫描停止。 交换基准 arr[0] (5) 和 arr[j] (3) 的元素 1 ：数组变为 [1, 2, 5, 5, 9, 6] 。此时基准 5 位于索引3。 分区结果：左子数组 [1, 2] (索引0-2)，基准 5 (索引3)，右子数组 [9, 6] (索引4-5)。 递归排序左子数组 [1, 2] : pivot=1 。 分区后， [1, 2] ，1已在正确位置，左子数组空，右子数组 [2] 。 递归排序 [2] ，单个元素，直接返回。左半部分完成。 递归排序右子数组 [9, 6] : pivot=9 。 分区后，交换 9 和 6 ，得到 [6, 9] ，9在正确位置。 左子数组 [6] 有序。右半部分完成。 最终有序数组 ：合并所有部分，得到 [1, 2, 5, 5, 6, 9] 。 关键点总结 时间复杂度 ：平均情况和最佳情况为 O(n log n)。最坏情况（当数组已有序或逆序，且基准选择不当时）会退化为 O(n²)。通过随机选择基准可以很大程度上避免最坏情况。 空间复杂度 ：主要是递归调用栈的深度，平均为 O(log n)，最坏为 O(n)。 稳定性 ：快速排序不是稳定的排序算法，因为在分区过程中，相等元素的相对位置可能会发生变化（例如上面例子中两个5的相对顺序可能改变）。