Java中的堆排序是一種基於比較的排序技術，其中使用了資料結構二元堆。這種排序與選擇排序幾乎相同，選擇最大的元素放在最後，然後對所有元素重複該過程。為了理解堆排序，讓我們看看Java中的二元堆排序。
在討論演算法之前，讓我們先看看 Heapify 是什麼。
廣告 該類別中的熱門課程 JAVA 掌握 - 專業化 | 78 課程系列 | 15 次模擬測驗使用輸入資料建立堆後，堆屬性可能不滿足。為了實現這一點，將使用一個名為 heapify 的函數來調整堆節點。如果我們想要建立一個最大堆，當前元素將與其子元素進行比較，如果子元素的值大於當前元素，則將與左或右子元素中最大的元素進行交換。類似地，如果需要建立最小堆，則將使用左子或右子元素中的最小元素進行交換。例如，以下是我們的輸入數組，
我們可以將其視為一棵樹而不是一個陣列。第一個元素將是根；第二個將是根的左子節點；第三個元素將是根的右子元素，依此類推。
為了將堆轉換為樹，請以自下而上的方向遍歷樹。由於葉節點沒有子節點，所以讓我們看看下一個層級。即 5 和 7。
我們可以從左邊的 5 點開始。這裡，5有兩個子節點：9和4，其中9大於父節點5。為了讓父節點更大，我們將交換5和9。交換後，樹將如下所示。
讓我們轉到下一個元素 7，其中 8 和 2 是子元素。與元素 9 和 4 類似，7 和 8 將被交換，如下圖所示。
最後，3 有兩個子節點 - 9 和 8，其中 9 在子節點和根節點中較大。因此，將交換 3 和 9 以使根更大。重複此過程，直到形成有效的堆，如下所示。
現在，讓我們嘗試使用給定的演算法對上面獲得的堆進行升序排序。首先，刪除最大的元素。即 root 並將其替換為最後一個元素。
現在，堆化形成的樹並將刪除的元素插入到陣列的最後一個，如下所示。
再次刪除根元素，將其替換為最後一個元素並對其進行堆疊。
將移除的元素插入空出的位置。現在您可以看到數組的末尾正在排序。
現在，刪除元素 7 並將其替換為 2。
堆積樹，如下圖所示。
重複這個過程，直到陣列排序完畢。刪除元素 5。
堆積樹。
刪除元素 4。
再次歡騰。
最後就會形成這樣一個排序數組。
現在讓我們來看看Java中堆排序的源碼
//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}輸出
堆排序是一種依賴二元堆資料結構的排序技術。它幾乎類似於選擇排序，並且不使用單獨的陣列進行排序和堆疊。
這是 Java 堆排序的指南。在這裡，我們討論工作的升序和降序排序演算法以及帶有範例程式碼的範例。您也可以閱讀我們其他推薦的文章以了解更多資訊 –
以上是Java 中的堆排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
