溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
堆是一種特殊的完全二叉樹，其特點是所有父節點都比子節點要小，或者所有父節點都比字節點要大。前一種稱為最小堆，后一種稱為最大堆。
比如下面這兩個：
那么這個特性有什么作用？既然題目是堆排序，那么肯定能用來排序。想要用堆排序首先要創建一個堆，如果對4 3 6 2 7 1 5這七個數字做從小到大排序，需要用這七個數創建一個最大堆，來看代碼：
public class HeapSort {
private int[] numbers;
private int length;
public HeapSort(int[] numbers) {
this.numbers = numbers;
this.length = numbers.length;
}
/**
* 調整二叉樹
* 如果父節點編號為x, 那么左子節點的編號是2x, 右子節點的編號是2x+1
* 節點編號從1開始, 對應數組中的索引是編號-1
* @param nodeId 節點編號, 從1開始
*/
public void adjust(int nodeId) {
int swapId;
int flag = 0; //是否需要繼續向下調整
while(nodeId * 2 <= this.length && flag == 0) {
//首先判斷它和左子節點的關系, 并用swapId記錄值較小的節點編號(最大堆是記錄較大的)
int index = nodeId - 1; //節點對應數組中數字的索引
int leftChild = nodeId * 2 - 1; //左子節點對應數組中數字的索引
int rightChild = nodeId * 2; //右子節點對應數組中數字的索引
if(numbers[index] < numbers[leftChild]) {
swapId = nodeId * 2;
} else {
swapId = nodeId;
}
//如果有右子節點, 再與右子節點比較
if(nodeId * 2 + 1 <= this.length) {
if(numbers[swapId - 1] < numbers[rightChild])
swapId = nodeId * 2 + 1;
}
//如果最小的節點編號不是自己, 說明子節點中有比父節點更小的
if(swapId != nodeId) {
swap(swapId, nodeId);
nodeId = swapId;
} else {
flag = 1;
}
}
}
/**
* 交換兩個節點的值
* @param nodeId1
* @param nodeId2
*/
public void swap(int nodeId1, int nodeId2) {
int t = numbers[nodeId1 - 1];
numbers[nodeId1 - 1] = numbers[nodeId2 - 1];
numbers[nodeId2 - 1] = t;
}
/**
* 創建最大堆
*/
public void createMaxHeap() {
//從最后一個非葉節點到第一個節點依次向上調整
for(int i = this.length / 2; i >= 1; i--) {
adjust(i);
}
}
public static void main(String[] args) {
int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
for(int x = 0; x < numbers.length; x++) {
System.out.print(numbers[x] + " ");
}
System.out.println();
HeapSort heap = new HeapSort(numbers);
heap.createMaxHeap();
}
}
對本例中的數列，從this.length / 2到1，共執行了三輪循環。
第一輪：
第二輪：
第三輪：
調整完成后，當前的二叉樹已經符合最大堆的特性，可以用來從小到大排序。堆排序的原理是，交換堆頂和最后一個節點的數字，即把最大的數字放到數組最后，然后對除了最大數的前n-1個數從新執行調整過程，使其符合最大堆特性。重復以上過程直到堆中只剩下一個數字。
public void sort() {
while(this.length > 1) {
swap(1, this.length);
this.length--;
adjust(1);
}
for(int x = 0; x < numbers.length; x++) {
System.out.print(numbers[x] + " ");
}
}
堆排序的時間復雜度和快速排序的平均時間復雜度一樣，是O(nlogn)。
總結
以上就是本文關于Java算法之堆排序代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：java實現的各種排序算法代碼示例、Java遺傳算法之沖出迷宮等，有什么問題可以隨時留言，小編會及時回復大家的。感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
