排序系列（六）--堆排序
?
//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?