深刻解析堆排序的算法思惟及Java代碼的完成演示。本站提示廣大學習愛好者：（深刻解析堆排序的算法思惟及Java代碼的完成演示）文章只能為提供參考，不一定能成為您想要的結果。以下是深刻解析堆排序的算法思惟及Java代碼的完成演示正文
1、基本常識
我們平日所說的堆是指二叉堆，二叉堆又稱完整二叉樹或許叫近似完整二叉樹。二叉堆又分為最年夜堆和最小堆。
堆排序(Heapsort)是指應用堆這類數據構造所設計的一種排序算法，它是選擇排序的一種。可以應用數組的特色疾速定位指定索引的元素。數組可以依據索引直接獲得元素，時光龐雜度為O（1），也就是常量，是以關於取值效力極高。
最年夜堆的特征以下：
最小堆的特征以下：
2、算法思惟
1.最年夜堆的算法思惟是：
先將初始的R[0…n-1]樹立成最年夜堆，此時是無序堆，而堆頂是最年夜元素
再將堆頂R[0]和無序區的最初一個記載R[n-1]交流，由此獲得新的無序區R[0…n-2]和有序區R[n-1]，且知足R[0…n-2].keys ≤ R[n-1].key
因為交流後，前R[0…n-2]能夠不知足最年夜堆的性質，是以再調劑前R[0…n-2]為最年夜堆，直到只要R[0]最初一個元素才調劑完成。
最年夜堆排序完成後，實際上是升序序列，每次調劑堆都是要獲得最年夜的一個元素，然後與以後堆的最初一個元故舊換，是以最初所獲得的序列是升序序列。
2.最小堆的算法思惟是：
先將初始的R[0…n-1]樹立成最小堆，此時是無序堆，而堆頂元素是最小的元素
再將堆頂R[0]與無序區的最初一個R[n-1]交流，由此獲得新的無序堆R[0…n-2]和有序堆R[n-1]，且知足R[0…n-2].keys >= R[n-1].key
因為交流後，前R[0…n-2]能夠不知足最小堆的性質，是以再調劑前R[0…n-2]為最小堆，直到只要R[0]最初一個元素才調劑完成
最小堆排序完成後，實際上是降序序列，每次調劑堆都是要獲得最小的一個元素，然後與以後無序堆的最初一個元故舊換，所以所獲得的序列是降序的。
提醒：堆排序的進程，其實就是赓續地擴展有序區，然後赓續地減少無序區，直到只要有序區的進程。
3、排序進程剖析
由於算法比擬籠統，這裡直接經由過程舉個小例子來講明堆排序的進程是若何的。上面我們用這個無序序列采取最年夜堆的停止堆排序，所獲得的序列就是升序序列（ASC）。
無序序列：89,-7,999,-89,7,0,-888,7,-7
第一步：初始化建成最年夜堆：
第二步：將堆頂最年夜元素999與無序區的最初一個元故舊換，使999成為有序區。交流後，-7成為堆頂，因為-7其實不是無序區中最年夜的元素，是以須要調劑無序區，使無序區中最年夜值89成為堆頂，所以-7與89交流。交流後招致89的右子樹不知足最年夜堆的性質，是以要對右子樹調劑成最年夜堆，所以-7要與0交流，以下圖：
從圖中看到，當-7成89交流後，堆頂是最年夜元素了，然則-7的左孩子是0，右孩子是-888，因為-7<0，招致-7這個結點不知足堆的性質，是以須要調劑它。所以，0與-7交流。
然後赓續反復著第二步的進程，直到全體成為有序區。
最初：所獲得的是升序序列
4、時光龐雜度
堆排序的時光，重要由樹立初始堆和重復調劑堆這兩部門的時光開支組成.因為堆排序是不穩固的，它得扭到的時光龐雜度會依據現實情形較年夜，是以只能取均勻時光龐雜度。
均勻時光龐雜度為：O( N * log2(N) )
堆排序耗時的操作有：初始堆 + 重復調劑堆，時光龐雜度以下：
1.初始建堆：每一個父節點會和閣下子節點停止最多2次比擬和1次交流，所以龐雜度跟父節點個數有關。依據2x <= n（x為n個元素可以折半的次數，也就是父節點個數），得出x = log2n。即O ( log2n )
2.重復調劑堆：因為初始化堆進程中，會記載數組比擬成果，所以堆排序對原序列的數組次序其實不敏感，最好情形和最壞情形差不多。須要抽取 n-1 次堆頂元素，每次取堆頂元素都須要重建堆（O(重建堆) < O(初始堆)）。所以小於 O(n-1) * O(log2n)
應用建議：
因為初始化堆須要比擬的次數較多，是以，堆排序比擬合適於數據量異常年夜的場所（百萬數據或更多）。因為高效的疾速排序是基於遞歸完成的，所以在數據量異常年夜時會產生客棧溢失足誤。
5、Java示例代碼
public class HeapSort{
private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12,
17,34,11};
public static void main(String[] args){
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
}
private static void buildMaxHeapify(int[] data){
//沒有子節點的才須要創立最年夜堆，從最初一個的父節點開端
int startIndex=getParentIndex(data.length-1);
//從尾端開端創立最年夜堆，每次都是准確的堆
for(int i=startIndex;i>=0;i--){
maxHeapify(data,data.length,i);
}
}
/**
*創立最年夜堆
*
*@paramdata
*@paramheapSize須要創立最年夜堆的年夜小，普通在sort的時刻用到，由於最多值放在末尾，末尾就不再歸入最年夜堆了
*@paramindex以後須要創立最年夜堆的地位
*/
private static void maxHeapify(int[] data,int heapSize,int index){
//以後點與閣下子節點比擬
int left=getChildLeftIndex(index);
int right=getChildRightIndex(index);
int largest=index;
if(left<heapSize&&data[index]<data[left]){
largest=left;
}
if(right<heapSize&&data[largest]<data[right]){
largest=right;
}
//獲得最年夜值後能夠須要交流，假如交流了，其子節點能夠就不是最年夜堆了，須要從新調劑
if(largest!=index){
int temp=data[index];
data[index]=data[largest];
data[largest]=temp;
maxHeapify(data,heapSize,largest);
}
}
/**
*排序，最年夜值放在末尾，data固然是最年夜堆，在排序後就成了遞增的
*
*@paramdata
*/
private static void heapSort(int[] data){
//末尾與頭交流，交流後調劑最年夜堆
for(int i=data.length-1;i>0;i--){
int temp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify(data,i,0);
}
}
/**
*父節點地位
*
*@paramcurrent
*@return
*/
private static int getParentIndex(int current){
return(current-1)>>1;
}
/**
*左子節點position留意括號，加法優先級更高
*
*@paramcurrent
*@return
*/
private static int getChildLeftIndex(int current){
return(current<<1)+1;
}
/**
*右子節點position
*
*@paramcurrent
*@return
*/
private static int getChildRightIndex(int current){
return(current<<1)+2;
}
private static void print(int[] data){
int pre=-2;
for(int i=0;i<data.length;i++){
if(pre<(int)getLog(i+1)){
pre=(int)getLog(i+1);
System.out.println();
}
System.out.print(data[i]+"|");
}
}
/**
*以2為底的對數
*
*@paramparam
*@return
*/
private static double getLog(double param){
return Math.log(param)/Math.log(2);
}
}
