Java中的快速排序

下面的文章《Java 中的快速排序》提供了 Java 中快速排序演算法的概述。快速排序演算法是一種高效率的排序演算法，與合併排序演算法類似。這是用於即時排序目的的常用演算法之一。此演算法最壞情況時間複雜度為 O(n^2)，平均情況時間複雜度為 O(n log n)，最好情況時間複雜度為 O(n log n)。

空間複雜度為 O(n log n)，其中 n 是輸入的大小。排序過程涉及輸入的分區、遞歸迭代以及為每個遞歸標記關鍵元素。此演算法中的排序類型涉及以迭代方式比較相鄰元素。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

Java 中的快速排序是如何運作的？

快速排序演算法可以在 Java 中實現，方法是形成偽代碼，並以有效的方式設計和遵循一系列步驟。

• 快速排序演算法的主要原理是基於分而治之的方法，也是一種高效的排序演算法。
• 輸入數組被劃分為子數組，劃分基於樞軸元素，即中心元素。主元元素兩側的子數組是實際進行排序的主要區域。
• 中心主元元素是將陣列分成兩個分區的基礎，其中左半部陣列元素小於主元元素，右半部陣列元素大於主元元素。
• 在考慮主元元素之前，它可以是陣列元素中的任何元素。為了便於理解，通常將其視為中間的或第一個或最後一個。主元元素可以是任意數組元素中的隨機元素。
• 在我們的範例中，陣列的最後一個元素被視為樞軸元素，其中子陣列的分割從陣列的右端開始。
• 最後，排序過程完成後，樞軸元素將處於其實際排序位置，其中排序的主要過程在於排序演算法的分區邏輯。
• 演算法的效率取決於子數組的大小以及它們的平衡方式。子數組越不平衡，時間複雜度越高，導致最壞情況的複雜度。
• 以隨機方式選擇主元元素在許多情況下會產生最佳時間複雜度，而不是選擇特定的開始、結束或中間索引作為主元元素。

用 Java 實作快速排序的範例

QuickSort演算法已使用Java程式語言實作如下，輸出程式碼已顯示在程式碼下方。

• 程式碼最初使用 QuickSortAlgo() 方法取得輸入，並以陣列、初始索引和最終索引（即陣列的長度）作為參數。
• 呼叫quickSortAlgo()方法後，它會檢查初始索引是否小於最終索引，然後呼叫arrayPartition()方法取得樞軸元素值。
• 分區元素包含根據樞軸元素周圍的元素值排列較小和較大元素的邏輯。
• 執行分區方法後得到主元索引後，會遞歸呼叫quickSortAlgo()方法，直到所有子數組完成分區和排序。
• 在分區邏輯中，最後一個元素被指定為樞軸元素，並且第一個元素與樞軸元素進行比較，即根據元素的大小進行交換。
• 這個遞歸過程會發生，直到陣列的所有元素都被分區和排序，最終結果是組合的排序數組。
• 只有當元素小於或等於主元元素時，才會在 for 迴圈迭代內交換元素。
• 完成迭代過程後，交換最後一個元素，即將主元元素值移至左側，從而進行新的分區，並以遞歸的形式重複相同的過程，從而產生一系列對不同可能的分區進行排序操作，作為給定數組元素的子數組的形成。
• 下面的程式碼可以在任何IDE上運行，並且可以透過更改main()中的數組值來驗證輸出。 main 方法僅用於取得控制台中的輸出。作為Java編碼標準的一部分，下面可以刪除main方法，並且可以建立一個對象，並且可以透過將它們設為非靜態來呼叫以下方法。

快速排序演算法的Java程式碼實作

以下是程式碼實作：

代碼：

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

輸出：

結論

與其他排序技術相比，快速排序演算法很高效，但不太穩定。當重複元素數量較多時，快速排序演算法的效率會下降，這是缺點。此快速排序演算法優化了空間複雜度。

以上是Java中的快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！