溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了深入淺析java中堆排序的原理，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
從堆排序的簡介到堆排序的算法實現等如下：
1. 簡介
堆排序是建立在堆這種數據結構基礎上的選擇排序，是原址排序，時間復雜度O(nlogn)，堆排序并不是一種穩定的排序方式。堆排序中通常使用的堆為最大堆。
2. 堆的定義
堆是一種數據結構，是一顆特殊的完全二叉樹，通常分為最大堆和最小堆。最大堆的定義為根結點最大，且根結點左右子樹都是最大堆；同樣，最小堆的定義為根結點最小，且根結點左右子樹均為最小堆。
最大堆滿足其每一個父結點均大于其左右子結點，最小堆則滿足其每一個父結點均小于其左右子結點。
3. 堆排序
3.1 堆的存放
在堆排序中，堆所表示的二叉樹并不需要使用指針的方式在計算機中存放，只需要使用數組即可，將樹的結點，從上至下，從左至右一個個放到數組中去。
因此，如果數組的起始索引為0，對于一個結點i來說，它的父結點索引為⌊i/2⌋，它的左子結點索引為2i+1，右子結點索引為2i+2。最后一個非葉子節點就是最后一個結點的父親，如果數組長度為n，那么其索引為⌊(n-1)/2⌋。
3.2 堆排序主要步驟
將無序序列構建成最大堆
將數組分成兩個區域，有序區和無序區，初始時創建一個整數i為數組的長度，用來劃分有序區和無序區，有序區初始為空。
將堆頂元素和最后一個無序區的元素交換，然后i-1。
調整使得所有無序區的元素重新為最大堆。
重復3，4步，直到 i = 0
3.3 堆的調整
假設有某棵完全二叉樹，其左右子樹均為最大堆，如何調整使得該二叉樹成為最大堆呢？如果根結點大于左右子結點，那么已經是最大堆了，無需調整。否則，交換根結點和左右子結點中較大的那個。假設交換的是左結點，那么目前這棵完全二叉樹右子樹仍然是一個最大堆，左子樹則不一定，但是左子樹的左右子樹還是最大堆，因此不斷遞歸下去調整即可。
因此，交換最后一個元素和堆頂元素后的調整步驟，就和上面所說的一致。而將無序序列構建成最大堆，同樣也可以運用這一點。從最后一個非葉子結點到第一個非葉子結點（根結點），對這些結點作為根結點的子樹，按順序調用一次上述描述的調整即可（每次調用時，該子樹的左右子樹必定是最大堆）。
4. 算法實現
#include <stdio.h>
void swap(int *a,int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
//左右子樹都是最大堆，從上至下調整使得最大堆, root_index是要調整的樹的根節點，length是無序區的長度
void adjust(int array[],int root_index,int length) {
int left_child = root_index*2+1;
int right_child = left_child+1;
int left_or_right = 0;
if((left_child >= length && right_child >= length) || (left_child >= length && array[root_index] >= array[right_child]) ||
(right_child >= length && array[root_index] >= array[left_child]) || (array[root_index] >= array[left_child] && array[root_index] >= array[right_child])){
return;
}
else if (array[left_child] >= array[root_index] && (right_child >= length || array[left_child] >= array[right_child])) {
left_or_right = 1;
}
else if (array[right_child] >= array[root_index] && (left_child >= length || array[right_child] >= array[left_child])) {
left_or_right = 0;
}
if(left_or_right) {
swap(&array[left_child],&array[root_index]);
adjust(array,left_child,length);
}
else {
swap(&array[right_child],&array[root_index]);
adjust(array,right_child,length);
}
}
//heapsort主遞歸，每一次將無序區最后一個元素與堆頂元素交換，將堆頂元素加入有序區，因此有序區加1,無序區減1，無序區只剩一個元素的時候遞歸終止
void heapsort_main(int array[],int length,int last_index) {
int i;
if(last_index == 0)
return;
swap(&array[0],&array[last_index]);
adjust(array,0,last_index);
heapsort_main(array,length,last_index-1);
}
//入口函數，array是待排序的數組，length是其長度
void heapsort(int array[],int length) {
int i;
for(i = length/2-1;i >= 0;i--) {
adjust(array,i,length);
}
heapsort_main(array,length,length-1);
}
int main(int argc,char *argv[]) {
int array[9] = {1,1,1,2,3,5,2,3,5};
heapsort(array,9);
int i;
for(i = 0;i < 9;i++) {
printf("%d ",array[i]);
}
}5.堆排序性質
時間復雜度O(nlogn)
空間復雜度O(1)
不穩定排序
上述內容就是深入淺析java中堆排序的原理，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
