快速排序（Quick Sort）是一種高效的排序算法，它使用分治法（Divide and Conquer）策略來把一個序列分為較小和較大的兩個子序列，然后遞歸地排序兩個子序列。
快速排序算法的基本思想：
-
選擇基準值（Pivot）：從數列中挑出一個元素，稱為“基準”（pivot）。
-
分區操作：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺放在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
-
遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。
快速排序的步驟：?
-
選擇基準：可以選擇第一個元素、最后一個元素、中間元素或者隨機元素作為基準。
-
分區：設置兩個指針，一個從左向右掃描（稱為
i），一個從右向左掃描（稱為j）。左指針i向右移動直到找到一個比基準大的元素，右指針j向左移動直到找到一個比基準小的元素。如果i?<?j，交換這兩個元素。重復這個過程直到i?>=?j。 -
交換基準：將基準值放到最終位置（即
i和j相遇的位置）。 -
遞歸排序：遞歸地對基準值左右兩側的子序列進行快速排序。
Java實現快速排序的示例代碼：?
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// pi是分區操作后基準值的正確位置int pi = partition(arr, low, high);// 分別對左右兩半部分進行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 選擇最后一個元素作為基準int i = (low - 1); // 小于區的邊界for (int j = low; j < high; j++) {// 如果當前元素小于或等于pivotif (arr[j] <= pivot) {i++;// 交換arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將pivot放到中間位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1; // 返回pivot的正確位置}public static void main(String args[]) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}}
}復雜度分析：?
-
時間復雜度：平均情況下為O(n log n)，最壞情況下為O(n^2)（例如，當輸入數組已經有序或接近有序時）。可以通過隨機選擇pivot或使用“三數取中法”等方法來優化性能。
-
空間復雜度：由于快速排序是遞歸實現的，其空間復雜度在最壞情況下為O(n)（遞歸棧的深度）。可以通過非遞歸方式（迭代方式）實現來降低空間復雜度。?
通過上述步驟和示例代碼，你可以在Java中實現快速排序算法。?
