/** *  */package com;/** * @author wenb * @time 下午03:52:55 * @date 2014-10-24 */public class HeapSort {    public static void main(String args[]){                  int[] a = {1,3,2,21,5,12,98,54};         headSort(a);          for(int i=0;i<a.length;i++){                         System.out.print(a[i]+" ");          }      }          public static int[] headSort(int[] sortArray){                  for(int i=0;i<sortArray.length-1;i++){                         buildMaxHeap(sortArray,sortArray.length-1-i);             swap(sortArray,0,sortArray.length-1-i);                     }               return sortArray;      }          //交换两个数据的方法      public static void swap(int[] data,int i,int j){                  int temp = data[i];          data[i] = data[j];          data[j] = temp;              }          //建立最大堆      public static void buildMaxHeap(int[] data,int lastIndex){                 //从lastIndex节点的父节点开始舰堆          for(int i=(lastIndex-1)/2;i>=0;i--){              //保存正在判断的节点              int k = i;              //这里为每个节点建立大顶堆,只要这个根节点还有子节点              while((2*k+1) <= lastIndex){                                  //假设左节点的值时最大的                  int biggerIndex = 2*k+1;                  //说明还有右节点是存在的                  if(biggerIndex < lastIndex){                      //选出子节点中最大的值                      if(data[biggerIndex] < data[biggerIndex+1]){                          biggerIndex++;                      }                  }                  //将跟节点与子节点进行比较                  if(data[k] < data[biggerIndex]){                      swap(data,k,biggerIndex);                      k = biggerIndex;                  }else{                                         break;                                     }              }          }      }   }