Go语言视频零基础入门到精通

javalearner

代码：

1. import java.util.Scanner;  
   
2. 
   
3. public class Heap {  
   
4.   
   
5.     private int[] data;  
   
6.   
   
7.     /*输入数组元素,数组下标从1开始*/  
   
8.     public void input() {  
   
9.         System.out.println("请输入数组大小");  
   
10.         Scanner scanner = new Scanner(System.in);  
    
11.         int n = scanner.nextInt();  
    
12.         data = new int[n + 1];  
    
13.         System.out.println("输入数组元素");  
    
14.         for (int i = 1; i <= data.length-1; i++) {  
    
15.             data[i] = scanner.nextInt();  
    
16.         }  
    
17.         System.out.println("输入完成");  
    
18.     }  
    
19.       //随机数据测试
    
20.     public void ramData(){
    
21.          int n=50;
    
22.          data = new int[n + 1];  
    
23.          for(int i=1;i<=n;i++)
    
24.            data[i]=java.util.concurrent.ThreadLocalRandom.current().nextInt(1000);
    
25.    }
    
26. 
    
27.    //测试数据：
    
28.    //第一组：1 7 9 3 10 16 4 14 2 8
    
29.   //第二组：17 8 84 2 45 94
    
30.    //第三组：10 32 1 9 5 7 12 0 4
    
31.    public static void main(String args[]){
    
32.           Heap h=new Heap();
    
33.               // h.input();
    
34.               h.ramData();
    
35.            System.out.println("堆排序前：");
    
36.                h.print();
    
37.                h.heapSort();
    
38.           System.out.println("========================================");
    
39.           System.out.println("堆排序后：");
    
40.               h.print();
    
41.   }
    
42.     /**
    
43.      * 调整堆，使其满足堆得定义
    
44.      * @param i
    
45.      * @param n
    
46.      */  
    
47.     public void adjust(int i, int n) {  
    
48.         
    
49.         int child;  
    
50.         for (; i <= n / 2; ) {  
    
51.             child = i * 2;  
    
52.            // System.out.println("child="+child);
    
53.             if(child+1<=n&&data[child]< data[child+1])  
    
54.                 child+=1;/*使child指向值较大的孩子*/  
    
55.             if(data[i]< data[child]){  
    
56.                 swap(i, child);  
    
57.                 /*交换后，以child为根的子树不一定满足堆定义，所以从child处开始调整*/  
    
58.                 i = child;  
    
59.                
    
60.             }  else break;
    
61.         }  
    
62.     }  
    
63.   
    
64.     public void heapSort() {  
    
65.         /*根据树的性质建堆，树节点前一半一定是分支节点，即有孩子的，所以我们从这里开始调整出初始堆*/  
    
66.         for (int i = data.length / 2; i > 0; i--)  
    
67.             adjust(i, data.length-1);  
    
68.         System.out.println("=================================================");
    
69.         System.out.println("调整后的初始堆：");
    
70.           print();
    
71.         for (int i = data.length-1; i > 0; i--) {  
    
72.             /*把根节点跟最后一个元素交换位置，调整剩下的n-1个节点，即可排好序*/  
    
73.             swap(1, i);  
    
74.             adjust(1, i - 1);  
    
75.         }  
    
76.     }  
    
77.   
    
78.     public void swap(int i, int j) {  
    
79.         int temp = data[i];  
    
80.         data[i] = data[j];  
    
81.         data[j] = temp;  
    
82.     }  
    
83.   
    
84.     public void print() {  
    
85.         for (int i = 1; i < data.length; i++) {  
    
86.             System.out.print(data[i]+" ");  
    
87.         }  
    
88.         System.out.println();  
    
89.     }  
    
90.   
    
91. }  
93. D:java>java   Heap
94. 堆排序前：
95. 0 118 895 186 366 996 689 21 612 346 873 521 121 729 485 704 822 231 462 553 588
96. 674 324 969 999 406 775 275 122 330 355 360 304 797 46 426 644 438 138 90 246 6
97. 49 210 9 99 837 626 724 759 842
98. =================================================
99. 调整后的初始堆：
100. 999 873 996 822 837 969 729 797 644 649 674 895 775 689 485 704 186 612 462 553
101. 588 118 626 759 842 406 121 275 122 330 355 360 304 21 46 426 231 438 138 90 246
102. 346 210 9 99 324 366 724 0 521
103. ========================================
104. 堆排序后：
105. 0 9 21 46 90 99 118 121 122 138 186 210 231 246 275 304 324 330 346 355 360 366
106. 406 426 438 462 485 521 553 588 612 626 644 649 674 689 704 724 729 759 775 797
107. 822 837 842 873 895 969 996 999

复制代码

解释:
建堆和调整
    如上，首先第一步，在对应的数组元素A, 左孩子A[2i], 和右孩子A[2i+1]中找到最大的那一个，将其下标存储在child中。如果A已经就是最大的元素，则调整直接结束。否则，i的某个子结点为最大的元素，将A[child]与A交换，从而使i及其子女都能满足最大堆性质。下标child所指的元素变成了A的值，会违反最大堆性质，所以对child所指元素为根的子树重新调整。如下，是此adjust的演示过程（下图是把4调整到最底层，一趟操作）：


    由上图，我们很容易看出，初始构造出一最大堆之后，在元素A，即16，大于它的俩个子结点4、10，满足最大堆性质。所以，i下调指向着4,小于,左子14，所以，调用adjust，4与其子，14交换位置。但4处在了14原来的位置之后，4小于其右子8，又违反了最大堆的性质，所以再递归调用adjust，将4与8，交换位置。于是，满足了最大堆性质，程序结束。 排序
  以下是，堆排序算法的演示过程（通过，顶端最大的元素与最后一个元素不断的交换，交换后又不断的调用adjust重新维持最大堆的性质，最后，一个一个的，从大到小的，把堆中的所有元素都清理掉，也就形成了一个有序的序列。这就是堆排序的全部过程。）：
上图中，a->b，b->c，....之间，都有一个顶端最大元素与最小元素交换后，调用adjust的过程  

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/6/000722500.zip