Java演算法之堆排序（HeapSort）

 1 import java.util.Arrays;
 2 
 3 publicclass HeapSort {
 4     inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
 5     public  HeapSort(){
 6        heapSort(a);
 7     }
 8 
 9     public  void heapSort(int[] a){
10         System.out.println("開始排序");
11         int arrayLength=a.length;
12         //循環建堆
13         for(int i=0;i<arrayLength-1;i++){
14             //建堆
15             buildMaxHeap(a,arrayLength-1-i);
16             //交換堆頂和最後一個元素
17             swap(a,0,arrayLength-1-i);
18             System.out.println(Arrays.toString(a));
19         }
20     }
21 
22  
23 
24     private  void swap(int[] data, int i, int j) {
25         // TODO Auto-generated method stub
26         int tmp=data[i];
27         data[i]=data[j];
28         data[j]=tmp;
29     }
30 
31     //對data數組從0到lastIndex建大頂堆
32     privatevoid buildMaxHeap(int[] data, int lastIndex) {
33         // TODO Auto-generated method stub
34         //從lastIndex處節點（最後一個節點）的父節點開始
35 
36         for(int i=(lastIndex-1)/2;i>=0;i--){
37             //k保存正在判斷的節點
38             int k=i;
39             //如果當前k節點的子節點存在
40             while(k*2+1<=lastIndex){
41                 //k節點的左子節點的索引
42                 int biggerIndex=2*k+1;
43                 //如果biggerIndex小於lastIndex，即biggerIndex+1代表的k節點的右子節點存在
44                 if(biggerIndex<lastIndex){
45                     //若果右子節點的值較大
46                     if(data[biggerIndex]<data[biggerIndex+1]){
47                         //biggerIndex總是記錄較大子節點的索引
48                         biggerIndex++;
49                     }
50                 }
51 
52                 //如果k節點的值小於其較大的子節點的值
53                if(data[k]<data[biggerIndex]){
54                     //交換他們
55                     swap(data,k,biggerIndex);
56                     //將biggerIndex賦予k，開始while循環的下一次循環，重新保證k節點的值大於其左右子節點的值
57                     k=biggerIndex;
58                 }else{
59                     break;
60                 }
61             }
62         }
63     }
64 }