堆排序
1.前提知識
堆：（英語：heap)是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱胡本。堆通常是一個可以被看做一棵樹的數(shù)組對象铲掐。
堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值渣蜗；
堆總是一棵完全二叉樹焙畔。
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆会涎。
優(yōu)先隊列(priority queue)
普通的隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加瑞凑，而從隊列頭刪除末秃。在優(yōu)先隊列中，元素被賦予優(yōu)先級籽御。當(dāng)訪問元素時练慕，具有最高優(yōu)先級的元素最先刪除惰匙。優(yōu)先隊列具有最高級先出 （first in, largest out）的行為特征。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)铃将。
a.完全二叉樹
若設(shè)二叉樹的深度為h项鬼，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到最大個數(shù)劲阎，第 h 層所有的結(jié)點都連續(xù)集中在最左邊绘盟，這就是完全二叉樹。
完全二叉樹是由滿二叉樹（一個二叉樹悯仙，如果每一個層的結(jié)點數(shù)都達到最大值龄毡，則這個二叉樹就是滿二叉樹。也就是說锡垄，如果一個二叉樹的層數(shù)為K沦零，且結(jié)點總數(shù)是(2^k) -1 ，則它就是滿二叉樹偎捎。）而引出來的蠢终。對于深度為K的，有n個結(jié)點的二叉樹茴她，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹寻拂。
(1)所有的葉結(jié)點都出現(xiàn)在第k層或k-l層（層次最大的兩層）
(2)對任一結(jié)點，如果其右子樹的最大層次為L丈牢，則其左子樹的最大層次為L或L+l祭钉。
一棵二叉樹至多只有最下面的兩層上的結(jié)點的度數(shù)可以小于2，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上己沛，則此二叉樹成為完全二叉樹慌核，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上，而在最后一層上申尼，右邊的若干結(jié)點缺失的二叉樹垮卓，則此二叉樹成為完全二叉樹。
b.小根堆和大根堆
假設(shè)有一棵完全二叉樹师幕，在滿足作為完全二叉樹的基礎(chǔ)上粟按，對于任意一個擁有父節(jié)點的子節(jié)點，其數(shù)值均不小于父節(jié)點的值霹粥；這樣層層遞推灭将，就是根節(jié)點的值最小，這樣的樹后控，稱為小根堆庙曙。
同理，又有一棵完全二叉樹浩淘，對于任意一個子節(jié)點來說捌朴，均不大于其父節(jié)點的值吴攒，如此遞推，就是根節(jié)點的值是最大的男旗，這樣的數(shù)舶斧，稱為大根堆。
2.一些規(guī)律
最后一個非葉節(jié)點的位置為nums.length-1察皇，所有擁有左右子節(jié)點的節(jié)點與子節(jié)點的位置關(guān)系為茴厉，假設(shè)子節(jié)點的編號為n，那么左子節(jié)點的編號為2n+1右節(jié)點的編號為2(n+1)
然后具體的做法為1.先建立大（惺踩佟）頂堆矾缓，2.交換堆頂?shù)奈恢煤驼{(diào)整整個堆，每調(diào)整一次堆的長度就減少一稻爬，直到堆的大小為0或1結(jié)束
3.先實現(xiàn)大頂堆
public static void main(String[] args) {
int[] array = new int[]{1,3,4,2,5};
heapsort(array);
其結(jié)構(gòu)就相當(dāng)于
然后我們先實現(xiàn)大頂堆
private static int[] heapsort(int[] array) {
buildBigheap(array);
}
從最后一個非葉節(jié)點的節(jié)點開始調(diào)整嗜闻，一直調(diào)整到根節(jié)點，這樣大頂堆就建立好了
private static void buildBigheap(int[] array) {
for(int i=array.length/2-1;i>-1;i--){ //從最后一個非葉節(jié)點的節(jié)點開始調(diào)整桅锄，一直調(diào)整到根節(jié)點
adjustheap(array,i,array.length);
}
然后是具體的調(diào)整過程：
private static void adjustheap(int[] array, int i,int end) {
//如果沒有左右子樹或者左右子樹現(xiàn)在已經(jīng)是拍好序的順序
if(2*i+1 >=end){
return;
}else if(2*(i+1)>=end){
if(array[2*i+1]>=array[i]){
swap(array,2*i+1,i);
}
}else{
//根已為最大
if(array[i]>=array[2*i+1]&&array[i]>=array[2*(i+1)]){
return;
//左子樹最大,交換后去排列左邊
}else if(array[2*i+1]>=array[i]&&array[2*i+1]>=array[2*(i+1)]){
swap(array,2*i+1,i);
adjustheap(array,2*i+1,end);
//右子樹最大琉雳，交換后去排列右邊
}else{
swap(array,2*(i+1),i);
adjustheap(array,2*(i+1),end);
}
}
}
**具體就是先判斷現(xiàn)在調(diào)整的位置，
A狀況說明(分成兩種情況：1.該節(jié)點是葉節(jié)點辫秧，2束倍，該節(jié)點往后的子節(jié)點已經(jīng)被拍好序了）
B狀況說明(因為當(dāng)一個節(jié)點只含有左子節(jié)點可以用的時候，那么他的右節(jié)點一定是空或者已經(jīng)排好序了）
C狀況說明(如果根最大什么都不用做盟戏，直接返回绪妹，如果左子節(jié)點最大，那么與根交換柿究，并對左子節(jié)點的剩余節(jié)點進行調(diào)整邮旷，同理可得右子節(jié)點）
OK
現(xiàn)在做完這一步我們可以看一下數(shù)組結(jié)構(gòu)
這個時候的根是最大的也就是已經(jīng)實現(xiàn)了大頂堆
4.交換堆頂元素與最后一個元素，實現(xiàn)排序
其實這一過程就是交換調(diào)整蝇摸，每一次交換都會使堆的需排序的大小減一廊移，那么很容易就想到當(dāng)堆大小為1時，調(diào)整完畢探入，所以用一個for循環(huán)for i array.length ->1
for(int i =array.length-1;i>0;i--){
swap(array,i,0); //交換棧頂元素與堆的最后一個數(shù)據(jù)（每次最后一個數(shù)據(jù)都會減一）
adjustheap(array,0,i); //調(diào)整堆為大頂堆
}
例如第一次交換后的數(shù)據(jù)為
然后調(diào)整完的數(shù)據(jù)為：
這樣做完后所有的序都已經(jīng)排好了
完整代碼
public static void main(String[] args) {
int[] array = new int[]{1,3,4,2,5};
heapsort(array);
for(int i=0;i<array.length;i++){
System.out.printf(array[i]+" ");
}
}
private static int[] heapsort(int[] array) {
buildBigheap(array);
return array;
}
private static void buildBigheap(int[] array) {
for(int i=array.length/2-1;i>-1;i--){
adjustheap(array,i,array.length);
}
for(int i =array.length-1;i>0;i--){
swap(array,i,0);
adjustheap(array,0,i);
}
}
private static void adjustheap(int[] array, int i,int end) {
//如果沒有左右子樹或者左右子樹現(xiàn)在已經(jīng)是拍好序的順序
if(2*i+1 >=end){
return;
}else if(2*(i+1)>=end){
if(array[2*i+1]>=array[i]){
swap(array,2*i+1,i);
}
}else{
//根已為最大
if(array[i]>=array[2*i+1]&&array[i]>=array[2*(i+1)]){
return;
//左子樹最大,交換后去排列左邊
}else if(array[2*i+1]>=array[i]&&array[2*i+1]>=array[2*(i+1)]){
swap(array,2*i+1,i);
adjustheap(array,2*i+1,end);
//右子樹最大，交換后去排列右邊
}else{
swap(array,2*(i+1),i);
adjustheap(array,2*(i+1),end);
}
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] =array[j];
array[j] = temp;
}
