排序算法：詳解快速排序
作者：farerboy
快速排序是一種高效的分治排序算法，由Tony Hoare在1960年提出。它的核心思想是"分而治之"，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
快速排序介紹
快速排序是一種高效的分治排序算法，由Tony Hoare在1960年提出。它的核心思想是"分而治之"，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
快速排序實現
一、工作原理
原始數組: [10, 7, 8, 9, 1, 5]
步驟1: 選擇基準元素(這里選擇最后一個元素5)
步驟2: 分區操作，將小于5的放在左邊，大于5的放在右邊
[1, 5, 8, 9, 10, 7] // 5已經在正確位置
步驟3: 遞歸排序左半部分[1]和右半部分[8, 9, 10, 7]
左半部分[1]已經有序
右半部分選擇基準7 → [7, 9, 10, 8] → 繼續遞歸...二、分區過程詳解
分區是快速排序的核心操作，以最后一個元素為基準：
數組: [10, 80, 30, 90, 40, 50, 70]
基準: 70
分區過程:
i = -1, j = 0: 10 < 70 → 交換arr[++i]和arr[j] → [10, 80, 30, 90, 40, 50, 70]
i = 0, j = 1: 80 > 70 → 不交換
i = 0, j = 2: 30 < 70 → 交換 → [10, 30, 80, 90, 40, 50, 70]
i = 1, j = 3: 90 > 70 → 不交換
i = 1, j = 4: 40 < 70 → 交換 → [10, 30, 40, 90, 80, 50, 70]
i = 2, j = 5: 50 < 70 → 交換 → [10, 30, 40, 50, 80, 90, 70]
最后交換基準: 交換arr[i+1]和arr[high] → [10, 30, 40, 50, 70, 90, 80]
基準70已經在正確位置！算法特點
圖片
代碼實現
一、基礎版（Lomuto分區方案）
public class QuickSortBasic {
/**
* 快速排序主方法
*/
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
/**
* 遞歸快速排序
* @param arr 待排序數組
* @param low 起始索引
* @param high 結束索引
*/
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 分區操作，獲取基準元素的正確位置
int pivotIndex = partition(arr, low, high);
System.out.println("基準元素 " + arr[pivotIndex] + " 已就位，數組狀態: "
+ arrayToString(arr, low, high));
// 遞歸排序左半部分
quickSort(arr, low, pivotIndex - 1);
// 遞歸排序右半部分
quickSort(arr, pivotIndex + 1, high);
}
}
/**
* Lomuto分區方案
* @return 基準元素的最終位置
*/
private static int partition(int[] arr, int low, int high) {
// 選擇最后一個元素作為基準
int pivot = arr[high];
System.out.println("分區: [" + low + "-" + high + "], 基準: " + pivot);
// i指向小于基準的區域的邊界
int i = low - 1;
for (int j = low; j < high; j++) {
// 如果當前元素小于或等于基準
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
if (i != j) {
System.out.println(" 交換 " + arr[j] + " 和 " + arr[i] +
" → " + arrayToString(arr, low, high));
}
}
}
// 將基準元素放到正確位置
swap(arr, i + 1, high);
System.out.println(" 基準就位: " + arrayToString(arr, low, 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;
}
/**
* 輔助方法：打印數組指定范圍
*/
private static String arrayToString(int[] arr, int low, int high) {
StringBuilder sb = new StringBuilder("[");
for (int i = low; i <= high; i++) {
sb.append(arr[i]);
if (i < high) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("原始數組: " + java.util.Arrays.toString(arr));
System.out.println("開始快速排序:");
quickSort(arr);
System.out.println("排序結果: " + java.util.Arrays.toString(arr));
}
}二、優化版（Hoare分區方案+三數取中）
public class OptimizedQuickSort {
/**
* 優化版快速排序
* 優化點1: 使用Hoare分區方案，減少交換次數
* 優化點2: 三數取中法選擇基準，避免最壞情況
* 優化點3: 小數組使用插入排序
*/
public static void quickSortOptimized(int[] arr) {
if (arr == null || arr.length <= 1) return;
quickSortOptimized(arr, 0, arr.length - 1);
}
private static void quickSortOptimized(int[] arr, int low, int high) {
// 小數組使用插入排序
if (high - low + 1 <= 10) {
insertionSort(arr, low, high);
return;
}
if (low < high) {
// 選擇基準并分區
int pivotIndex = hoarePartition(arr, low, high);
// 遞歸排序
quickSortOptimized(arr, low, pivotIndex);
quickSortOptimized(arr, pivotIndex + 1, high);
}
}
/**
* Hoare分區方案 - 更高效的分區方法
*/
private static int hoarePartition(int[] arr, int low, int high) {
// 三數取中法選擇基準
int pivot = medianOfThree(arr, low, high);
int i = low - 1;
int j = high + 1;
while (true) {
// 從左向右找到第一個大于等于基準的元素
do {
i++;
} while (arr[i] < pivot);
// 從右向左找到第一個小于等于基準的元素
do {
j--;
} while (arr[j] > pivot);
// 如果指針相遇，返回分區位置
if (i >= j) {
return j;
}
// 交換元素
swap(arr, i, j);
}
}
/**
* 三數取中法：選擇左、中、右三個數的中值作為基準
*/
private static int medianOfThree(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
// 對三個數進行排序
if (arr[low] > arr[mid]) swap(arr, low, mid);
if (arr[low] > arr[high]) swap(arr, low, high);
if (arr[mid] > arr[high]) swap(arr, mid, high);
// 將中值放在high-1位置，返回中值作為基準
swap(arr, mid, high);
return arr[high];
}
/**
* 插入排序，用于小數組
*/
private static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
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 = {64, 34, 25, 12, 22, 11, 90, 5, 77, 30, 15, 42};
System.out.println("原始數組: " + java.util.Arrays.toString(arr));
quickSortOptimized(arr);
System.out.println("排序結果: " + java.util.Arrays.toString(arr));
}
}使用建議
- 推薦使用：大規模數據排序、通用排序需求
- 避免使用：需要穩定排序的場景、對最壞性能要求嚴格的場景
- 優化重點：合理的基準選擇、處理小數組、避免最壞情況
快速排序以其優異的平均性能和緩存友好性，成為實際應用中最常用的排序算法之一！
責任編輯：武曉燕
來源：
小林聊編程
