樹形選擇排序的實作

package cn.itcast.sort;

public class SelectSort {  

 //這裡傳遞過來的是一個Integer類型的數組

 public static void treeSelectSort(Object[] a){    

     int len = a.length;  

     int treeSize = 2 * len - 1;  //完全二叉樹的節點數  

     int low = 0;  

     //臨時的樹存儲空間 ，是以我們不會直接使用樹形選擇排序到實際工程中

     Object[] tree = new Object[treeSize];   

      //由後向前填充此樹，索引從0開始  

      for(int i = len-1,j=0 ;i >= 0; --i,j++){

      //填充葉子節點，treeSize-1是最後一個節點  

          tree[treeSize-1-j] = a[i];  

      }  

      //填充非終端節點  

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

          tree[(i-1)/2] = ((Comparable)tree[i-1]).compareTo(tree[i]) < 0 ? tree[i-1]:tree[i];  

        }  

      //不斷移走最小節點  

      int minIndex;  

      while(low < len){  

          Object min = tree[0];    //最小值  

          a[low++] = min;  

          minIndex = treeSize-1;         

          //找到最小值的索引  

          while(((Comparable)tree[minIndex]).compareTo(min)!=0){  

              minIndex--;  

          }  

          tree[minIndex] = Integer.MAX_VALUE;  //設定一個最大值标志  

         //找到其兄弟節點  

         while(minIndex > 0){      

         //如果其還有父節點  

         //如果是右節點  ,左節點minIndex-1與右節點minIndex比較

            if(minIndex % 2 == 0){  

                  tree[(minIndex-1)/2] = ((Comparable)tree[minIndex-1]).compareTo(tree[minIndex])  

                       < 0 ? tree[minIndex-1]:tree[minIndex];  

                  minIndex = (minIndex-1)/2;  

              }else{                  

              //如果是左節點 ，左節點minIndex與右節點minIndex+1比較

                   tree[minIndex/2] = ((Comparable)tree[minIndex]).compareTo(tree[minIndex+1])  

                      < 0 ? tree[minIndex]:tree[minIndex+1];  

                   minIndex = minIndex/2;  

              }  

          }  

      }  

   }  

   public static void main(String[] args) {

       Integer[] data = {49,38,65,97,76,13,27,49};  

       SelectSort.treeSelectSort(data);  

       for(Integer d:data){  

           System.out.println(d);  

       }  

   }  

}  

輸出結果：