【排序算法】快速排序詳解--附詳細流程代碼

快速排序算法

介紹

快速排序（Quick Sort）是一種高效的分治排序算法，由英國計算機科學家 Tony Hoare 于 1960 年提出。它是實際應用中最常用的排序算法之一。快速排序的基本思想是：選擇一個"基準"（pivot）元素，通過一次排序將待排序列分割成獨立的兩部分，一部分所有元素均小于基準，另一部分所有元素均大于基準，然后遞歸地對這兩部分分別進行快速排序。分治策略的運用讓快速排序在平均情況下能達到 O(nlogn) 的時間復雜度，大大優于簡單排序算法的 O(n2) 性能。

算法步驟

從數列中選擇一個元素作為"基準"（pivot），本文采用最左側元素作為基準
將所有比基準值小的元素放到基準前面，所有比基準值大的元素放到基準后面（分區操作）
對基準左右兩個子序列分別重復步驟1和2，直到子序列只有一個元素或為空

核心特性

分治策略：將問題分解為更小的子問題，逐步解決
原地排序：只需要 O(logn) 的額外空間復雜度（主要用于遞歸調用的棧空間）
時間復雜度：平均情況為 O(nlogn)，最壞情況為 O(n2)，最好情況為 O(nlogn)
不穩定性：相等元素的相對位置在排序后可能會改變
高效性：在實際應用中，快速排序通常是最快的排序算法之一

基礎實現

接下來大家一起看下快速排序的部分主流語言實現：

代碼實現

Java實現

public class QuickSort {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[low];int i = low + 1;for (int j = low + 1; j <= high; j++) {if (arr[j] < pivot) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;}}int temp = arr[low];arr[low] = arr[i - 1];arr[i - 1] = temp;return i - 1;}public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};System.out.println("排序前的數組：");printArray(arr);quickSort(arr, 0, arr.length - 1);System.out.println("排序后的數組：");printArray(arr);}
}

注意，在上述代碼里，通過：

for (int j = low + 1; j <= high; j++) {if (arr[j] < pivot) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;}
}

將小于基準的元素移到左側，然后通過：

int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;

修正基準的位置，實現基準左側都小于基準、基準右側大于等于基準。

優化策略

隨機選擇基準元素

使用最左側元素作為基準可能會在數組已經排序或接近排序時導致最壞性能，隨機選擇基準可以降低這種風險：

private static int randomPartition(int[] arr, int low, int high) {int randomIndex = low + (int)(Math.random() * (high - low + 1));int temp = arr[randomIndex];arr[randomIndex] = arr[low];arr[low] = temp;return partition(arr, low, high);
}

三數取中法

選擇左端、中間和右端三個元素的中值作為基準，可以進一步優化快速排序：

private static int medianOfThreePartition(int[] arr, int low, int high) {int mid = low + (high - low) / 2;if (arr[mid] < arr[low])swap(arr, mid, low);if (arr[high] < arr[low])swap(arr, high, low);if (arr[high] < arr[mid])swap(arr, high, mid);swap(arr, mid, low);return partition(arr, low, high);
}

優缺點

優點

平均情況下非常高效，時間復雜度為 O(nlogn)
原地排序，空間復雜度低
緩存友好，數據局部性好
適合處理大規模數據
在許多實際應用中表現優秀

缺點

最壞情況下性能退化至 O(n2)，比如當數組已經排序時
不穩定的排序算法
對于小數組，快速排序可能比其他基礎排序慢
遞歸實現可能導致棧溢出（可以使用迭代方式解決）

應用場景

需要高效排序大量數據的情況
作為系統庫中的排序函數（如 C++ 的 std::sort、Java 的 Arrays.sort）
需要就地排序且對空間復雜度敏感的場景
需要平均情況下高性能的應用

擴展

雙軸快速排序

Java 的 Arrays.sort() 使用的是雙軸快速排序，它使用兩個樞軸(基準)，可以進一步提高性能：

public static void dualPivotQuickSort(int[] arr, int low, int high) {if (high <= low) return;if (arr[low] > arr[high]) {int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}int pivot1 = arr[low];int pivot2 = arr[high];int lt = low + 1;    int gt = high - 1;   int i = low + 1;     while (i <= gt) {if (arr[i] < pivot1) {int temp = arr[lt];arr[lt] = arr[i];arr[i] = temp;lt++;i++;} else if (arr[i] > pivot2) {int temp = arr[i];arr[i] = arr[gt];arr[gt] = temp;gt--;} else {i++;}}arr[low] = arr[lt - 1];arr[lt - 1] = pivot1;arr[high] = arr[gt + 1];arr[gt + 1] = pivot2;dualPivotQuickSort(arr, low, lt - 2);dualPivotQuickSort(arr, lt, gt);dualPivotQuickSort(arr, gt + 2, high);
}