Heap_Sort

 1 public class Heap_Sort {
 2     
 3     public static void print(int[] a){
 4         for(int i : a){
 5             System.out.println(i);
 6         }
 7     }
 8     
 9     //调整堆为大根堆
10     public static void ajustTree(int[] a, int i , int len){
11         int max = i; //记录父节点和两个子节点中的最大者，默认为父节点
12         if(i <= len/2 ){ //如果不是叶子节点
13             if(2 * i + 1 <= len && a[max] < a[2 * i + 1]){//如果父节点小于左子节点
14                 max = 2 * i + 1;
15             }
16             if(2 * (i + 1) <= len && a[max] < a[2 * (i + 1)]){//如果较大的节点小于右子节点
17                 max = 2 * (i + 1);
18             }
19             if(max != i){ //如果节点发生了交换 重新调整堆 为大根堆
20                 int temp = a[i];
21                 a[i] = a[max];
22                 a[max] = temp;
23                 ajustTree(a, max, len);
24             }
25         }
26     }
27     
28     //进行排序
29     public static void sort(int[] a,int len){
30         int temp;
31         for(int i = len -1 ;i > 0 ;i--){//从最后一个叶子节点开始
32             temp = a[i];
33             a[i] = a[0];
34             a[0] = temp;
35             ajustTree(a ,0 ,i-1);//最后一个元素已有序 不需再调整
36         }
37     }
38     
39     
40     public static void main(String[] args){
41         int[] a = {4,1,6,3,8,2,10,5,9,11,7};
42         int len = a.length;
43         
44         //初始化堆为大根堆  从最后一个非叶子节点开始
45         for(int i = len/2 - 1; i >= 0; i--){
46             ajustTree(a, i ,len-1);
47         }
48         sort(a, len);
49         print(a);
50     }
51 }