堆排序

把数组转换成堆，一个一个删除最小值存储起来。代码如下,存储元素由于从0开始，所以下滤(percolatDown)的时候0要额外判断。源码如下。

public class Test {

private static int currentSize;

public static void main(String[]args) {

int []is= {0,3,52,33,1,2,4,6,9,7,3,6,3,4,2,78,54,67,398,5};

currentSize = is.length -1;

          buildHeap(is);

          for(int i=0;i<is.length;i++)

          {

         System.out.println(deleteMin(is));

          }

//         heapSort(is);

//          for(int i=0;i<is.length;i++)

//          {

//         System.out.println(is[i]);

//          }

    }

public static void buildHeap(int []is)

{

for(int count = currentSize/2;count>=0;count--)

{

            percolateDown(count, is);

}

}

private static void percolateDown(int index,int []is) {

int child = index;

while(child<currentSize)

{

child =child*2+1;

if(child<currentSize||child==1){

if(is[child]<is[child+1])

{

child++;

}

else 

{

}

if(is[child]>is[index])

{

int s = is[child];

is[child] =  is[index];

is[index] = s;

index =child;

}

}

}

}

public  static int deleteMin(int []is)

{

int min = is[0];

is[0] = is[currentSize--];

percolateDown(0, is);

return min;

}

public static void  heapSort(int []is) {

for(int i=0;i<is.length;i++)

     {

      int x = deleteMin(is);

      is[currentSize+1]=x;

     }

}

}