一、什么是堆排序
? ? ? ? 堆排序是將數(shù)組看做一個完全二叉樹(附錄里有二叉樹的解釋)，具有以下的性質(zhì)：
1）每個節(jié)點的值都大于子節(jié)點的值，叫做大頂堆。
2）每個節(jié)點的值都小于子節(jié)點的值，叫做小頂堆。
二、堆排序的實現(xiàn)原理
? ? ? ? 大頂堆是將數(shù)組按照升序的方式進行排序。原理是：
（1）從最后一個根節(jié)點開始，比較父節(jié)點和兩個子節(jié)點的值，如果子節(jié)點的值大于父節(jié)點，則交換兩點的數(shù)值，否則不交換。
（2）從最后一個根節(jié)點依次比較到頂點 ，也就是上圖0節(jié)點的位置。這樣進行一輪比較之后，得到的0節(jié)點的數(shù)值就是該數(shù)組中最大的數(shù)值。
（3）再將0節(jié)點的數(shù)值與該數(shù)組最后一個子節(jié)點的數(shù)值進行交換。這是最后一個子節(jié)點位置上的值便是該數(shù)組中最大的值。
（4）這時，把數(shù)組的倒數(shù)第二個子節(jié)點當做數(shù)組的結(jié)尾，再次將0節(jié)點作為父節(jié)點進行大頂堆操作，這樣重復到數(shù)組的結(jié)尾為1節(jié)點，數(shù)組排序完成。
（5）將數(shù)組輸出可以看到該數(shù)組變?yōu)橐粋€升序的數(shù)組。
? ? ? ? 小頂堆則與大頂堆正好相反。
三、代碼實現(xiàn)：
package JavaDay_13
publc class Heapsort {
public static void main(String[] args) {?
?????????????int[] arr = {1,5,6,8,7,2,3,4,9,4,15,12}; //創(chuàng)建一個數(shù)組
? ? ? ? ? ? ?heapSort(arr); //調(diào)用heapSort方法進行第一次排序，選出最大值放在0節(jié)點
????????????for(int i=0;i<arr.length;i++){? ?//將arr數(shù)組輸出
? ? ? ? ? ? ? ? ? ? System.out.print(arr[i]+" ");
????????????}
}
public static void heapSort(int[]arr){
? ? ? ? ? ? ? int n= arr.length-1;
? ? ? ? ? ? ?for(int i=n/2-1;i>=0;i++){? ? ? ? ? ? //從最后一個根節(jié)點開始，直到0節(jié)點位置
? ? ? ? ? ? ? ? ?heapAdjust(arr,i,n);? ? ? ? ? ? ? ? // 傳入?yún)?shù)arr數(shù)組，父節(jié)點 i ，數(shù)組長度n
?????????????????????}?
? ? ? ? ? ? for(int i=n;i>0;i--) {? ? ? ? ? ? ? ? ? ? //從最后一個節(jié)點開始，到取到倒數(shù)第二個節(jié)點
?????????????????????swap(arr,i);? ? ? ? ? ? ? ? ? ? ? //調(diào)用方法，將此時的 i 與arr數(shù)組的第一個值交換
? ? ? ? ? ? ? ? ? ? ?heapAdjust(arr,0,i-1);? ? ? ? //再次構(gòu)建大頂堆
?????????????????????}
?}?
?????public static void heapAdjust(int[] arr,int parent,int length) {?
?????????????????????int temp = arr[parent];? ? ? ? ? ? ? ? ?//設置一個初始值記錄arr[parent]的數(shù)值
? ? ? ? ? ? ? ? for(int i=parent*2+1;i<=length;i=i*2+1) {?
?// i為父節(jié)點的左節(jié)點，每次循環(huán)結(jié)束后，i節(jié)點成為父節(jié)點，i迭代為自己之前的數(shù)的左節(jié)點
? ? ? ? ? ? ? ? ? ? ? ? ? if(i<length && arr[i]<arr[i+1]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????? i++;? ? ? //如果i的左節(jié)點小于右節(jié)點，則i+1變?yōu)橛夜?jié)點
????????????????????????????????????}
?????????????????????????????????if(temp>arr[i])? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????break;? ? // 如果左右節(jié)點中較大的值小于父節(jié)點，則跳出
? ? ? ? ? ????????????????????????? }
? ? ? ? ????????????? ????? arr[parent] = arr[i];? ?//讓父節(jié)點的值變?yōu)閕節(jié)點的值
? ? ? ? ? ? ? ? ? ? ? ? ? ?parent = i;? ? ? ? ? ? //此時父節(jié)點變?yōu)閕；
? ? ? ? ? ? ? ? ? ?}
? ? ? ? arr[parent] = temp;? ? ? ? ? ? //? 將剛剛得到的父節(jié)點賦值給新位置
? ? }
? ? public static void swap(int[] arr,int i) {? //將數(shù)組arr中的i的值與0交換
? ? ? ? ????????????int temp = arr[0];
? ? ? ? ????????????arr[0] = arr[i];
? ? ? ? ????????????arr[i] = temp;
????????? ? }
}
附錄：
????????在計算機科學中，二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”。
????????完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹。
