快速排序是計算機科學中最經典的排序算法之一，由 Tony Hoare 在 1960 年提出。它憑借平均時間復雜度 O (nlogn)、原地排序（空間復雜度 O (logn)，主要來自遞歸棧）以及良好的實際性能，成為工業界處理大規模數據排序的首選算法之一。無論是在 LeetCode 算法題中，還是在考研計算機專業基礎綜合（408）的考試里，快速排序都是高頻考點。

快速排序算法核心思路

快速排序的核心思想是分治法（Divide and Conquer），通過選擇一個 “基準元素” 將數組分為兩部分，使得左半部分的元素都小于等于基準，右半部分的元素都大于等于基準，然后遞歸地對兩部分進行排序。

?關鍵步驟解析

（1）選擇基準元素（Pivot）

基準元素的選擇對快速排序的性能影響很大。常見的選擇策略有：

• 固定位置：如選擇數組的第一個元素、最后一個元素或中間元素。

• 隨機選擇：隨機挑選數組中的一個元素作為基準，避免在有序數組上出現最壞情況。

• 三數取中：選擇數組第一個、中間和最后一個元素中的中位數作為基準，平衡性能。

本文以 “選擇最后一個元素作為基準” 為例進行講解，后續會在優化部分介紹其他策略。

（2）分區操作（Partition）

分區是快速排序的核心，目的是將數組劃分為兩部分，使得左部分元素≤基準，右部分元素≥基準。經典的 Lomuto 分區算法步驟如下：

1. 設基準元素為pivot = arr[right]（right為當前數組的右邊界）。

1. 初始化指針i，指向 “小于等于基準區域” 的邊界（初始為left - 1）。

1. 遍歷數組從left到right - 1：

• • 若arr[j] ≤ pivot，則i右移一位，交換arr[i]與arr[j]，將當前元素納入 “小于等于基準區域”。

1. 遍歷結束后，交換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 (n2)），可優化基準選擇策略（如隨機選擇基準）。

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 (n2)（隨機化后最壞情況概率極低）。

• 空間復雜度：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 (n2)（隨機化后概率極低）。

• 空間復雜度：O (logn)，來自遞歸棧。

考研 408 例題解析

例題 1：基本概念與時間復雜度分析（選擇題）

題目：下列關于快速排序的敘述中，正確的是（ ）。

A. 快速排序的時間復雜度為 O (nlogn)，空間復雜度為 O (n)

B. 快速排序是穩定的排序算法

C. 快速排序在最壞情況下的時間復雜度為 O (n2)，此時數組已基本有序

D. 快速排序的分區操作可以通過一次線性掃描完成

答案：C、D

解析：

• A 錯誤：快速排序空間復雜度為 O (logn)（遞歸棧），而非 O (n)。

• B 錯誤：快速排序不穩定（分區交換可能改變相等元素的相對順序）。

• C 正確：當數組有序或逆序時，每次分區只能將數組分為 1 和 n-1 兩部分，時間復雜度退化至 O (n2)。

• D 正確：經典分區算法通過一次線性掃描（遍歷數組）即可完成。

例題 2：算法設計題（408 高頻考點）

題目：已知一個整數數組A[0..n-1]，設計一個算法，將所有負數移到正數之前（0 視為正數），要求不改變負數之間的相對順序和正數之間的相對順序，且時間復雜度為 O (n)，空間復雜度為 O (1)。

解題思路：本題雖不直接考查排序，但可借鑒快速排序的分區思想。與快速排序不同的是，本題要求保持相對順序（穩定），但題目限制空間復雜度為 O (1)，因此不能使用額外數組。我們可以通過類似 “冒泡” 的方式，將負數逐步交換到前面，但時間復雜度會變為 O (n2)。不過，考研中更可能的考點是理解分區思想的變形應用。

優化思路：若允許空間復雜度為 O (n)，可使用雙指針 + 輔助數組：

1. 遍歷原數組，將負數依次放入輔助數組前半部分，正數放入后半部分。

1. 將輔助數組復制回原數組。

但根據題目限制（空間 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（相對順序改變）}}}

考研答題要點：

1. 說明快速排序分區思想的核心：通過一次遍歷劃分區域。

1. 指出本題限制（保持相對順序）與快速排序的差異。

1. 給出符合時間和空間復雜度的解法（如輔助數組法，并說明其穩定性）。

例題 3：快速排序與其他排序算法對比（綜合題）

題目：比較快速排序、歸并排序和堆排序的優缺點，并說明在什么情況下選擇快速排序更合適。

答案要點：

• 快速排序：

• • 優點：平均時間復雜度 O (nlogn)，原地排序（空間 O (logn)），實際性能優異。

• • 缺點：不穩定，最壞時間復雜度 O (n2)，對有序數組敏感。

• • 適用場景：數據量大、分布隨機、

希望本文能夠幫助讀者更深入地理解快速排序，并在實際項目中發揮其優勢。謝謝閱讀！

---

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。