Java排序算法 堆排序

1991年計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert

W．Floyd)和威廉姆斯(J．Williams)在1964年共同發明了著名的堆排序算法( Heap Sort

)。本文主要介紹堆排序用Java來實作。

AD：

堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素。堆排序是不穩定的排序方法，輔助空間為O(1)，

最壞時間複雜度為O(nlog2n) ，堆排序的堆序的平均性能較接近于最壞性能。 

堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在目前無序區中選取最大(或最小)關鍵字的記錄變得簡單。

（1）用大根堆排序的基本思想

① 先将初始檔案R[1..n]建成一個大根堆,此堆為初始的無序區

②

再将關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key

③由于交換後新的根R[1]可能違反堆性質，故應将目前無序區R[1..n-1]調整為堆。然後再次将R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要将R[1..n-2]調整為堆。

……

直到無序區隻有一個元素為止。

（2）大根堆排序算法的基本操作： 

① 初始化操作：将R[1..n]構造為初始堆；

每一趟排序的基本操作：将目前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後将新的無序區調整為堆(亦稱重建堆)。

注意： 

①隻需做n-1趟排序，選出較大的n-1個關鍵字即可以使得檔案遞增有序。

②用小根堆排序與利用大根堆類似，隻不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐漸擴大至整個向量為止。

代碼實作：

public class HeapSort  {

    public

static void main(String[] args)  

    {

int[] a = {26, 5, 77, 1, 61, 11, 59, 15, 48, 19};

Sort(a);  

    }

////小堆排序

static void Sort(int[] a)  

int n = a.length;  

int temp = 0;  

Display(a, "Before sort : ");  

for(int i=n/2; i>0; i--)  

Adjust(a, i-1, n);  

for(int i=n-2; i>=0; i--)  

{  

temp = a[i+1];  

a[i+1] = a[0];  

a[0] = temp;  

Adjust(a, 0, i+1);  

}  

Display(a, "After  sort : ");

public  static void Adjust(int[] a, int i, int n)

int j = 0;  

temp = a[i];    

j = 2 * i + 1;  

while(j <= n-1)  

if(j < n-1 && a[j]

< a[j+1])  

j++;  

if(temp >= a[j])  

break;  

a[(j-1)/2] = a[j];  

j = 2 * j + 1;

Display(a, "----- ");  

a[(j-1)/2] = temp;  

static void Display(int[] a, String str)  

System.out.println(str);  

for(int i=0; i<a.length; i++)

System.out.print(a[i] + " ");  

System.out.println();  

} 

計算詳細為：

Before sort :

26 5 77 1 61 11 59 15 48 19

-----

26 5 77 48 61 11 59 15 48 19

26 61 77 48 61 11 59 15 1 19

26 61 77 48 19 11 59 15 1 19

77 61 77 48 19 11 59 15 1 5

77 61 59 48 19 11 59 15 1 5

61 61 59 48 19 11 26 15 1 77

61 48 59 48 19 11 26 15 1 77

61 48 59 15 19 11 26 15 1 77

59 48 59 15 19 11 26 5 61 77

59 48 26 15 19 11 26 5 61 77

48 48 26 15 19 11 1 59 61 77

48 19 26 15 19 11 1 59 61 77

26 19 26 15 5 11 48 59 61 77

26 19 11 15 5 11 48 59 61 77

19 19 11 15 5 26 48 59 61 77

19 15 11 15 5 26 48 59 61 77

15 15 11 1 19 26 48 59 61 77

11 5 11 15 19 26 48 59 61 77

5 5 11 15 19 26 48 59 61 77

After  sort :

1 5 11 15 19 26 48 59 61 77