Java演算法之堆排序（HeapSort）

 import java.util.Arrays;

 publicclass HeapSort {

     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};

     public  HeapSort(){

        heapSort(a);

     }

     public  void heapSort(int[] a){

         System.out.println("開始排序");

         int arrayLength=a.length;

         //循環建堆

         for(int i=0;i<arrayLength-1;i++){

             //建堆

             buildMaxHeap(a,arrayLength-1-i);

             //交換堆頂和最後一個元素

             swap(a,0,arrayLength-1-i);

             System.out.println(Arrays.toString(a));

         }

     }

     private  void swap(int[] data, int i, int j) {

         // TODO Auto-generated method stub

         int tmp=data[i];

         data[i]=data[j];

         data[j]=tmp;

     }

     //對data數組從0到lastIndex建大頂堆

     privatevoid buildMaxHeap(int[] data, int lastIndex) {

         // TODO Auto-generated method stub

         //從lastIndex處節點（最後一個節點）的父節點開始

         for(int i=(lastIndex-1)/2;i>=0;i--){

             //k保存正在判斷的節點

             int k=i;

             //如果當前k節點的子節點存在

             while(k*2+1<=lastIndex){

                 //k節點的左子節點的索引

                 int biggerIndex=2*k+1;

                 //如果biggerIndex小於lastIndex，即biggerIndex+1代表的k節點的右子節點存在

                 if(biggerIndex<lastIndex){

                     //若果右子節點的值較大

                     if(data[biggerIndex]<data[biggerIndex+1]){

                         //biggerIndex總是記錄較大子節點的索引

                         biggerIndex++;

                     }

                 }

                 //如果k節點的值小於其較大的子節點的值

                if(data[k]<data[biggerIndex]){

                     //交換他們

                     swap(data,k,biggerIndex);

                     //將biggerIndex賦予k，開始while循環的下一次循環，重新保證k節點的值大於其左右子節點的值

                     k=biggerIndex;

                 }else{

                     break;

                 }

             }

         }

     }

 }