Java常見排序算法之堆排序

在學習算法的過程中，我們難免會接觸很多和排序相關的算法。總而言之，對于任何編程人員來說，基本的排序算法是必須要掌握的。

從今天開始，我們將要進行基本的排序算法的講解。Are you ready？Let‘s go~~~

1、排序算法的基本概念的講解

???? 時間復雜度:需要排序的的關鍵字的比較次數和相應的移動的次數。

???? 空間復雜度:分析需要多少輔助的內存。

???? 穩定性:如果記錄兩個關鍵字的A和B它們的值相等，經過排序后它們的位置沒有發生交換，那么我們稱這個排序算法是穩定的。

????????????? 否則我們稱這個排序算法是不穩定的。

???

??? 排序算法的常見分類:

??? 1、內部排序（最常見的一種排序方式，不需要借助第三方輔助存儲工具）

??? 2、外部排序（需要借助外部存儲來輔助完成相關的排序操作）

??????? 如果參與排序的數據元素非常的多，數據量非常的大，計算機無法把整個排序過程放到內存中進行的話，

??????? 我們必須借助外部存儲器如磁盤來完成，這種排序方式，我們稱之為外部排序。

??????? 其中外部排序最常見的就是多路歸并排序，即將原始文件分解成多個能夠一次性裝入內存的部分，分別把每一部分調入

??????? 內存完成相應的排序，接下來在對多個有序的外部文件進行多路歸并排序。

??

?? 對于我們絕大多數的程序員而言，我們經常遇到的為內部排序。接下來我們將要對常見的內部排序進行相應的講解。

??? 今天要講解的內部排序為:

?? ?堆排序

? 1、堆排序的基本概念的講解

???? 堆排序是一個樹形選擇排序方法，它的特點是：在排序過程中，將L[1...n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹

??? 中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大（或最小）的元素。

???堆的定義如下：n個關鍵字序列L[1...n]稱為堆，當且僅當該序列滿足：

???①L(i)<=L(2i)且L(i)<=L(2i+1)

???②L(i)>L(2i)且L(i)>=L(2i+1)(1<=i<=[n/2])

???滿足第一種情況的堆稱為小根堆（小頂堆），

???滿足第二種情況的堆稱為大根堆（大頂堆）。

???算法思想：對于構造初始堆，就是一個反復篩選的過程。

???n個結點的完全二叉樹，最后一個結點是第【n/2】個結點為根的孩子。

?? 對第【n/2】個結點為根的子樹篩選，使該子樹成為堆。

?? 之后向前依次對各結點（【n/2】-1~1）為根的子樹進行篩選，看該結點值是否大于其左右結點的值，

???若不是，將左右結點中較大值與之交換，交換后可能會破壞下一級的堆，于是繼續采用上述方法構造

? ?下一級的堆，直到以該結點的子樹構造成堆為止。

?? 反復利用上述調整堆的方法建堆，直到根節點為止。

? 2、堆排序之Java代碼實現

?

package com.yonyou.test;/*** 內部排序算法之堆排序* 默認按照從小到大進行排序操作* @author 小浩* @創建日期 2015-3-24*/
public class Test{public static void main(String[] args) {//需要進行排序的數組int[] array=new int[]{8,3,2,1,7,4,6,5};//輸出原數組的內容printResult(array);//進行堆排序操作for(int i=array.length-1;i>0;i--){//進行n-1次建大頂堆，每次建堆，都把最小的值放到根位置上面//同時在每次建堆的過程中選出最大的值作為根//創建大頂堆的過程也是創建完全二叉樹的過程buildMaxHeap(array,i);}//輸出排序后的相關結果printResult(array);}/*** 建立大頂堆的過程* @param array* @param i*/private static void buildMaxHeap(int[] array, int i) {//從葉子節點的第一個父節點開始循環for(int j=(i-1)/2;j>=0;j--){   //最后一個節點并且這棵樹只有左子樹if((2*j+1==i)&&(i%2!=0)){if(array[j]<array[2*j+1])swap(array,j,2*j+1);}else{if(array[j]<array[2*j+1])swap(array,j,2*j+1);if(array[j]<array[2*j+2])swap(array,j,2*j+2);}}swap(array,0,i);}/*** 輸出相應數組的結果* @param array*/private static void printResult(int[] array) {for(int value:array)		System.out.print(" "+value+" ");System.out.println();}/*** 交換數組中兩個變量的值* @param array* @param i* @param j*/private static void swap(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;}
}

　　3.堆排序的效率分析

??? 時間復雜度:假設有n個數據，數據交換的次數最多為n-1次，但程序的總體的比較次數較多。所以綜合考慮有直接選擇排序的時間復雜度為O(n2)

?? (n的平方)。所以當記錄占用字節數較多時，通常比直接插入排序的執行速度快些。

??? 空間復雜度:直接選擇排序的空間復雜度很好，它只需要一個附加單元用于數據交換，所以其空間復雜度為O(1)。

??? 穩定性:由于在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩定的排序方法。

?

?? 好吧，直接選擇排序的講解就先到這里了。

??

?