核心思路

快速排序是Java中Arrays.sort()的實現原理，采用分治策略，通過選擇基準元素，將數組分為兩個子數組，使得左邊元素 ≤ 基準元素 ≤ 右邊元素，然后遞歸排序子數組。

舉個簡單的例子，圖書管理員需要按照書本厚度對一箱書進行排序，使用快速排序就是先選擇一本書作為中間基準，把厚的書放在它右邊，薄的書放在它左邊。（這里左右兩邊內部是無序的）

處理完后再對它左邊的書分別快速排序（即選出新的基準元素，厚的放右邊，薄的放左邊），同理右邊也是一樣，最后就得到完整的序列。

復雜度

情況	時間復雜度	空間復雜度
?最好情況?	O(n logn)	O(logn)
?最壞情況?	O(n2)	O(n)
?平均情況?	O(n logn)	O(logn)

優缺點

優點：

1. 平均情況下最快的比較排序算法
2. 原地排序（不需要額外內存）
3. 高度可優化

缺點：

1. 最壞情況時間復雜度較高
2. 不穩定排序
3. 遞歸實現需要棧空間

適用場景：

• 大規模數據排序
• 需要高效率的通用排序
• 內存受限環境

代碼實現（Java）

public class QuickSort {public static void main(String[] args) {int[] arr = {5, 3, 8, 4, 2};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr)); }public static void quickSort(int[] arr, int low, int high) {if (low < high) {//選出基準元素int pivotIndex = partition(arr, low, high);//排序左半部quickSort(arr, low, pivotIndex - 1);  //排序右半部quickSort(arr, pivotIndex + 1, high); }}/*** 分區（這里以最后一個元素為基準）*/private static int partition(int[] arr, int low, int high) {//基準元素int pivot = arr[high]; //小元素區間的左邊界int i = low - 1;       //i+1實際上就是最后基準元素要被移到的位置for (int j = low; j < high; j++) {//把小于基準的元素不斷向左靠攏（比基準大的元素也被動地向右邊移動），//最后[low,i]的元素都比基準小，那么i+1的位置自然就留給基準元素了if (arr[j] <= pivot) {i++;swap(arr, i, j);}}//移動基準元素swap(arr, i + 1, high); return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

排序過程

初始數組：[5, 3, 8, 4, 2]

第1次分區（pivot=2）

移動元素：5>2，3>2，8>2，4>2 → 無交換  
最終交換基準 → [2, 3, 8, 4, 5]
返回位置0

遞歸左半部（空數組）和右半部[3,8,4,5]

第2次分區（pivot=5）

排序數組：[3,8,4,5]  
移動元素：3<5，8>5，4<5 → 交換8和4  
最終數組：[3,4,5,8]  
返回位置2

遞歸處理左右子數組

左半部[3,4] → 最終排序[3,4]  
右半部[8] → 保持原樣

最終結果

[2, 3, 4, 5, 8]