大家好，今天我們來聊聊快速排序（QuickSort）算法，這個經典的排序算法被廣泛應用于各種需要高效排序的場景。作為一種分治法（Divide and Conquer）算法，快速排序的效率在平均情況下非常高，是大多數排序算法中的“黃金選手”。那么，讓我們一起來了解如何在 Java 中實現快速排序吧！
一、什么是快速排序？
快速排序是一種基于分治法的排序算法，它的基本思想是通過選擇一個“基準”元素，將待排序的數組分成兩個子數組，使得一個子數組的所有元素都小于基準元素，另一個子數組的所有元素都大于基準元素。然后對這兩個子數組遞歸執行快速排序，最終完成排序。
快速排序的步驟：
- 從數組中選擇一個元素作為“基準”（pivot）。
- 將數組中所有比基準小的元素移到基準的左邊，比基準大的元素移到基準的右邊。
- 遞歸地對基準左邊和右邊的子數組進行排序。
- 當子數組的大小為 1 或者 0 時，停止遞歸，因為它們已經是有序的。
二、快速排序的時間復雜度
快速排序的時間復雜度是O(n log n)，但在最壞情況下（比如每次選取的基準元素都是最小或最大的元素），它的時間復雜度會退化到O(n2)。然而，在平均情況下，快速排序的表現非常優秀，因此它通常被認為是高效的排序算法之一。
- 最好和平均時間復雜度：O(n log n)
- 最壞時間復雜度：O(n2)
- 空間復雜度：O(log n)
三、Java 快速排序的實現
在 Java 中實現快速排序，我們需要編寫一個遞歸函數來進行分割和排序。具體步驟如下：
- 選擇基準元素：常見的選擇方式是選取數組的第一個元素、最后一個元素、或隨機選擇一個元素作為基準。
- 劃分數組：通過一個指針將數組分成兩個部分，一部分小于基準，另一部分大于基準。
- 遞歸排序子數組：對左邊和右邊的子數組分別遞歸執行快速排序。
下面是 Java 實現快速排序的代碼：
public class QuickSort {public static void sort(int[] arr, int left, int right) {//遞歸跳出條件：每個左右子數組的長度為1，大于和等于都要有if (left >= right) {return;}//基準數int base = arr[left];int i = left;int j = right;while (i < j) {//注意先從右向左找，注意沒有等號while (arr[j] > base && j > i) {j--;}//再從左往右找，注意要有等號while (arr[i] <= base && i < j) {i++;}//如果因為i = j跳出循環，那么沒必要進行交換if (i < j) {//交換兩元素位置int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}//交換基準與i=j的位置arr[left] = arr[i];arr[i] = base;//左右子數組遞歸排序sort(arr,left, i - 1);sort(arr, i + 1, right);}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);}
}
四、代碼解析
-
quickSort方法：這是快速排序的遞歸入口函數。它接收一個數組和數組的下標low和high，表示待排序數組的范圍。如果low小于high，就調用partition方法來劃分數組并遞歸排序。 -
partition方法：該方法用于選擇基準元素并將數組劃分為兩部分：- 所有小于基準的元素排在基準的左邊。
- 所有大于基準的元素排在基準的右邊。 最后，基準元素會被放到它的正確位置，并返回該位置的索引。
-
swap方法：用于交換數組中兩個元素的位置。 -
printArray方法：用于打印數組，便于觀察排序結果。
五、輸出結果
假設我們使用的數組是 {10, 7, 8, 9, 1, 5}，那么運行上述代碼后的輸出將會是：
原始數組：
10 7 8 9 1 5
排序后的數組：
1 5 7 8 9 10
可以看到，數組成功地按照從小到大的順序進行了排序。
六、優化與擴展
-
選擇基準優化：
- 在選擇基準時，避免總是選取第一個或最后一個元素，可以通過三數取中法來選擇基準元素，從而避免在已經部分有序的數組中出現最壞情況（O(n2)）。
示例：
int mid = low + (high - low) / 2; int pivot = medianOfThree(arr[low], arr[mid], arr[high]); -
尾遞歸優化：
快速排序是遞歸的，遞歸深度可能較深。通過尾遞歸優化，可以將較小的子數組放在棧中，而將較大的子數組先處理，減少棧的深度。 -
非遞歸實現：
快速排序也可以通過棧實現非遞歸版本，避免遞歸過深導致棧溢出。
七、小結
快速排序是一個高效的排序算法，通過分治法將問題逐步簡化。盡管它在最壞情況下的時間復雜度是 O(n2)，但在平均情況下，其表現非常優異，尤其是在處理大量數據時。如果能優化基準選擇，快速排序的效率會進一步提升。希望通過本文的介紹，你對快速排序有了更深入的了解，并且能夠在 Java 中輕松實現這一經典算法！
工具)
