快速排序是计算机科学中最经典的排序算法之一，由 Tony Hoare 在 1960 年提出。它凭借平均时间复杂度 O (nlogn)、原地排序（空间复杂度 O (logn)，主要来自递归栈）以及良好的实际性能，成为工业界处理大规模数据排序的首选算法之一。无论是在 LeetCode 算法题中，还是在考研计算机专业基础综合（408）的考试里，快速排序都是高频考点。

快速排序算法核心思路

快速排序的核心思想是分治法（Divide and Conquer），通过选择一个 “基准元素” 将数组分为两部分，使得左半部分的元素都小于等于基准，右半部分的元素都大于等于基准，然后递归地对两部分进行排序。

关键步骤解析

（1）选择基准元素（Pivot）

基准元素的选择对快速排序的性能影响很大。常见的选择策略有：

固定位置：如选择数组的第一个元素、最后一个元素或中间元素。

随机选择：随机挑选数组中的一个元素作为基准，避免在有序数组上出现最坏情况。

三数取中：选择数组第一个、中间和最后一个元素中的中位数作为基准，平衡性能。

本文以 “选择最后一个元素作为基准” 为例进行讲解，后续会在优化部分介绍其他策略。

（2）分区操作（Partition）

分区是快速排序的核心，目的是将数组划分为两部分，使得左部分元素≤基准，右部分元素≥基准。经典的 Lomuto 分区算法步骤如下：

设基准元素为pivot = arr[right]（right为当前数组的右边界）。

初始化指针i，指向 “小于等于基准区域” 的边界（初始为left - 1）。

遍历数组从left到right - 1：

- 若arr[j] ≤ pivot，则i右移一位，交换arr[i]与arr[j]，将当前元素纳入 “小于等于基准区域”。

遍历结束后，交换arr[i + 1]与arr[right]，此时基准元素被放置在正确位置（i + 1），左边元素均≤基准，右边元素均≥基准。

（3）递归排序

分区操作后，基准元素将数组分为左右两个子数组。递归地对左子数组（[left, i]）和右子数组（[i + 2, right]）执行快速排序，直到子数组长度为 0 或 1（此时数组已有序）。

Java 实现（基础版）

public class QuickSortBasic {// 对外暴露的排序方法public static void sort(int[] arr) {if (arr == null || arr.length <= 1) {return;}quickSort(arr, 0, arr.length - 1);}// 递归执行快速排序private static void quickSort(int[] arr, int left, int right) {if (left < right) {int pivotIndex = partition(arr, left, right); // 分区quickSort(arr, left, pivotIndex - 1); // 左子数组排序quickSort(arr, pivotIndex + 1, right); // 右子数组排序}}// 分区操作private static int partition(int[] arr, int left, int right) {int pivot = arr[right]; // 选择最后一个元素作为基准int i = left - 1; // 小于等于基准区域的边界for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j); // 将当前元素纳入小于等于基准区域}}swap(arr, i + 1, right); // 放置基准元素到正确位置return i + 1; // 返回基准位置}// 交换数组中两个元素private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 测试public static void main(String[] args) {int[] arr = {4, 7, 2, 5, 1, 3, 6};sort(arr);for (int num : arr) {System.out.print(num + " "); // 输出：1 2 3 4 5 6 7}}}

LeetCode 例题实战

例题 1：912. 排序数组（中等）

题目描述：给你一个整数数组 nums，请你将该数组升序排列。

示例：

输入：nums = [5,2,3,1]

输出：[1,2,3,5]

解题思路：直接使用快速排序对数组进行排序。由于 LeetCode 的测试用例可能包含大量重复元素或有序数组，为避免最坏情况（时间复杂度退化至 O (n²)），可优化基准选择策略（如随机选择基准）。

Java 代码实现：

class Solution {public int[] sortArray(int[] nums) {if (nums == null || nums.length <= 1) {return nums;}quickSort(nums, 0, nums.length - 1);return nums;}private void quickSort(int[] nums, int left, int right) {if (left < right) {int pivotIndex = randomPartition(nums, left, right); // 随机选择基准quickSort(nums, left, pivotIndex - 1);quickSort(nums, pivotIndex + 1, right);}}// 随机选择基准并分区private int randomPartition(int[] nums, int left, int right) {// 生成[left, right]范围内的随机索引int randomIndex = left + (int) (Math.random() * (right - left + 1));swap(nums, randomIndex, right); // 将随机基准交换到末尾return partition(nums, left, right); // 执行分区}private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

复杂度分析：

时间复杂度：平均 O (nlogn)，最坏 O (n²)（随机化后最坏情况概率极低）。

空间复杂度：O (logn)，来自递归栈。

例题 2：215. 数组中的第 K 个最大元素（中等）

题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

解题思路：利用快速排序的分区思想（快速选择算法）。每次分区后，基准元素的位置 pivotIndex 是其在有序数组中的最终位置。若 pivotIndex = n - k（n 为数组长度），则该元素即为第 k 个最大元素；若 pivotIndex < n - k，则在右子数组中继续查找；否则在左子数组中查找。

Java 代码实现：

class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;int targetIndex = n - k; // 第k大元素在有序数组中的索引return quickSelect(nums, 0, n - 1, targetIndex);}private int quickSelect(int[] nums, int left, int right, int targetIndex) {if (left == right) {return nums[left]; // 子数组长度为1时直接返回}int pivotIndex = randomPartition(nums, left, right);if (pivotIndex == targetIndex) {return nums[pivotIndex]; // 找到目标元素} else if (pivotIndex < targetIndex) {return quickSelect(nums, pivotIndex + 1, right, targetIndex); // 右子数组查找} else {return quickSelect(nums, left, pivotIndex - 1, targetIndex); // 左子数组查找}}// 随机分区（同例题1）private int randomPartition(int[] nums, int left, int right) {int randomIndex = left + (int) (Math.random() * (right - left + 1));swap(nums, randomIndex, right);return partition(nums, left, right);}private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

复杂度分析：

时间复杂度：平均 O (n)，最坏 O (n²)（随机化后概率极低）。

空间复杂度：O (logn)，来自递归栈。

考研 408 例题解析

例题 1：基本概念与时间复杂度分析（选择题）

题目：下列关于快速排序的叙述中，正确的是（）。
A. 快速排序的时间复杂度为 O (nlogn)，空间复杂度为 O (n)
B. 快速排序是稳定的排序算法
C. 快速排序在最坏情况下的时间复杂度为 O (n²)，此时数组已基本有序
D. 快速排序的分区操作可以通过一次线性扫描完成
答案：C、D
解析：
A 错误：快速排序空间复杂度为 O (logn)（递归栈），而非 O (n)。
B 错误：快速排序不稳定（分区交换可能改变相等元素的相对顺序）。
C 正确：当数组有序或逆序时，每次分区只能将数组分为 1 和 n-1 两部分，时间复杂度退化至 O (n²)。
D 正确：经典分区算法通过一次线性扫描（遍历数组）即可完成。

例题 2：算法设计题（408 高频考点）

题目：已知一个整数数组A[0..n-1]，设计一个算法，将所有负数移到正数之前（0 视为正数），要求不改变负数之间的相对顺序和正数之间的相对顺序，且时间复杂度为 O (n)，空间复杂度为 O (1)。

解题思路：本题虽不直接考查排序，但可借鉴快速排序的分区思想。与快速排序不同的是，本题要求保持相对顺序（稳定），但题目限制空间复杂度为 O (1)，因此不能使用额外数组。我们可以通过类似 “冒泡” 的方式，将负数逐步交换到前面，但时间复杂度会变为 O (n²)。不过，考研中更可能的考点是理解分区思想的变形应用。

优化思路：若允许空间复杂度为 O (n)，可使用双指针 + 辅助数组：

遍历原数组，将负数依次放入辅助数组前半部分，正数放入后半部分。

将辅助数组复制回原数组。

但根据题目限制（空间 O (1)），这里提供基于分区思想的解法（注意：该方法可能改变相对顺序，仅作思路参考）：

public class PartitionNegatives {public static void partitionNegatives(int[] A) {if (A == null || A.length <= 1) {return;}int i = -1; // 负数区域边界for (int j = 0; j < A.length; j++) {if (A[j] < 0) { // 遇到负数i++;swap(A, i, j); // 交换到负数区域}}}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}public static void main(String[] args) {int[] A = {1, -2, 3, -4, 5, -6};partitionNegatives(A);for (int num : A) {System.out.print(num + " "); // 输出：-2 -4 -6 1 3 5（相对顺序改变）}}}

考研答题要点：

说明快速排序分区思想的核心：通过一次遍历划分区域。

指出本题限制（保持相对顺序）与快速排序的差异。

给出符合时间和空间复杂度的解法（如辅助数组法，并说明其稳定性）。

例题 3：快速排序与其他排序算法对比（综合题）

题目：比较快速排序、归并排序和堆排序的优缺点，并说明在什么情况下选择快速排序更合适。
答案要点：
快速排序：
优点：平均时间复杂度 O (nlogn)，原地排序（空间 O (logn)），实际性能优异。
缺点：不稳定，最坏时间复杂度 O (n²)，对有序数组敏感。
适用场景：数据量大、分布随机、

希望本文能够帮助读者更深入地理解快速排序，并在实际项目中发挥其优势。谢谢阅读！

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。