排序系列（六）--堆排序

 

//author:lilywangcn

public class HeapSort {

private static int[] array=new int[]{10,30,20,4,9,-1,10,6,15};

/**

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

print();

buildsort();

print();

}

public static void buildHeap(){

for(int i=array.length/2-1; i>=0; i--){

heapify(i,array.length-1);

}

}

private static void buildsort(){

buildHeap();

for(int last=array.length-1;last>=0;last--){

int tmp=array[0];

array[0]=array[last];

array[last]=tmp;

heapify(0,last-1);

}

}

private static void heapify(int top,int end){

int large=top*2+1;

int tmp=array[top];

while(large<=end){

if(large<end){

if(array[large]<array[2*top+2]) 

large=large + 1;

}

if(tmp>array[large]) break;

else{

array[top]=array[large];

array[large]=tmp;

top=large;

large=2*top+1;

}

print();

}

}

private static void print(){

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

System.out.print(array[i]+" ");

}

System.out.println("");

}

 

 

}

算法复杂度：O(nlogn)，算法不稳定

 

运行结果：

 

10 30 20 4 9 -1 10 6 15 

10 30 20 15 9 -1 10 6 4 

30 10 20 15 9 -1 10 6 4 

30 15 20 10 9 -1 10 6 4 

20 15 4 10 9 -1 10 6 30 

20 15 10 10 9 -1 4 6 30 

15 6 10 10 9 -1 4 20 30 

15 10 10 6 9 -1 4 20 30 

10 4 10 6 9 -1 15 20 30 

10 9 10 6 4 -1 15 20 30 

10 9 -1 6 4 10 15 20 30 

9 4 -1 6 10 10 15 20 30 

9 6 -1 4 10 10 15 20 30 

6 4 -1 9 10 10 15 20 30 

4 -1 6 9 10 10 15 20 30 

-1 4 6 9 10 10 15 20 30