HeapImpl

package com.liuxt.sort.impl;

import com.liuxt.sort.Sort;

public class HeapImpl implements Sort {

  /**  * 用堆排序算法实现对数组的递增排序。  * 基本思想：  *   先按对的定义排列成一个序列输出堆的最小关键字（对小顶堆而言），然后将剩余的关键字最调整为新堆。  *   得到次小的关键字，反复知道所有的关键字都有序。  *    *  时间复杂度o(nlogn)  *  空间复杂度  * @param data  */  public void sortData(int[] data) {   int i=0,t=0;   int n=data.length;   for(i=n/2-1;i>=0;--i)    heapadjust(data,i,n-1);   for(i=n-1;i>0;--i){    t=data[0];    data[0]=data[i];    data[i]=t;    heapadjust(data,0,i-1);   }    }

 /**  * 将一个整数数组中的元素调整成大根堆  * @param data  * @param s  * @param m  */ private void heapadjust(int[] data, int s, int m) {  /**data[s..m]所构成的一个元素序列中，除了data[s]外，其余元素均满足堆的定义**/  /**调整元素data[s]的位置，使data[s..m]成为一个大根堆**/  int t,j;  t=data[s];// 备份元素data[s],为以后找到适合的位置后插入  for(j=2*s+1;j<m;j=j*2+1){ //沿着值较大的孩子节点向下筛选。   if(j<m&&data[j]<data[j+1]) ++j; //j是值较大的元素的索引下标   if(!(t<data[j])) break; //用s记录待插入元素的下标。   data[s]=data[j];s=j; //插入备份元素。  }//end for  data[s]=t; }

}