Java中的快速排序演算法

java中的快速排序，也稱為分區交換排序，是一種分而治之的排序演算法。快速排序是最好地利用 CPU 快取的演算法的一個很好的例子，因為它具有分而治之的性質。快速排序演算法是最常用的排序演算法之一，尤其是對大型列表進行排序，並且大多數程式語言都實現了它。快速排序演算法將原始資料分成兩部分：單獨排序，然後合併產生排序資料。

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

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

讓我們考慮陣列 {8, 6, 3, 4, 9, 2, 1, 7} 需要使用快速排序進行排序。

實作快速排序演算法的步驟

1.從陣列中選擇一個名為「樞軸」的元素。一般情況下，選擇中間的元素作為樞軸。讓我們以 4 為基準。

2.將陣列重新排列為兩部分，使得小於主元的元素出現在主元之前，大於主元的元素出現在主元之後。遵循以下步驟：

• 選取最左邊的元素，即8；由於4是樞軸，而8比4大，所以8需要移到4的右側；在右側，我們保留7，因為它大於4，並選擇1與8 交換，因此交換後陣列變成：1,6,3,4,9,2,8,7
• 選取左下一個元素，即6；由於4是樞軸，且6比4大，所以6需要移到4的右側；在右側，我們保留7,8，因為它們大於4，並選擇2 與6 交換，因此交換後陣列變成：1,2,3,4,9,6,8,7
• 現在，由於主元左側的所有元素都小於主元，且主元右側的所有元素都大於主元，因此我們以 4 作為主元。

3.對左子數組（元素少於主元的數組）和右子數組（元素多於主元的數組）遞歸應用步驟 1 和 2。如果數組僅包含一個或零個元素，則該數組被視為分類數組。

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

這是一個使用快速排序演算法對整數數組進行排序的 java 程式。

代碼：

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

輸出：

快速排序演算法的優點

以下是快速排序演算法的優點：

• 優異的引用局部性：引用局部性是處理器在短時間內重複存取相同記憶體位置的能力。由於快取未命中次數極少，java 中的快速排序提供了出色的引用局部性，這在現代架構中對於效能至關重要。
• 快速排序是可並行的：一旦完成將數組劃分為較小區域的初始步驟，所有單獨的子數組就可以並行獨立排序。由於這個原因，快速排序效能更好。

快速排序的複雜度分析

快速排序是一種快速尾遞歸演算法，遵循分而治之的原則。以下是最佳、平均和最壞情況下的複雜度分析：

• 最佳情況複雜度：如果陣列或清單包含 n 個元素，則第一次運行將需要 O(n)。現在對剩餘的兩個子數組進行排序需要 2*O (n/2)。由此得出最好情況下複雜度為 O(n logn) 的結論。
• 平均情況複雜度：快速排序的平均情況為 O (n log n)。
• 最壞情況複雜性：選擇第一個或最後一個會導致近排序或近逆排序資料的最壞情況效能。快速排序在最壞情況下執行 O(n^2)。

 在 Java 中，陣列。 Sort() 方法使用快速排序演算法對陣列進行排序。

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