1. package lhz.algorithm.chapter.six; 
2. /** 
3.  * “堆排序”，《算法导论》6.4章节 
4.  * 利用之前实现的构建MaxHeap和MaxHeapify算法完成排序。 
5.  * 伪代码： 
6.  * HEAPSORT(A) 
7.  * 1 BUILD-MAX-HEAP(A) 
8.  * 2 for i ← length[A] downto 2 
9.  * 3 do exchange A[1] ↔ A[i] 
10.  * 4 heap-size[A] ← heap-size[A] - 1 
11.  * 5 MAX-HEAPIFY(A, 1) 
12.  * @author lihzh(苦逼coder) * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/738164  */ 
13. public class HeapSort { 
14.      
15.     private static int[] input = new int[] {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; 
16.  
17.     public static void main(String[] args) { 
18.         //堆排序 
19.         heapSort(); 
20.         //打印数组 
21.         printArray(); 
22.     } 
23.      
24.     /** 
25.      * 堆排序，《算法导论》原文摘要： 
26.      * The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input 
27.      * array A[1  n], where n = length[A]. Since the maximum element of the array is stored at the 
28.      * root A[1], it can be put into its correct final position by exchanging it with A[n].  
29.      * If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that  
30.      * A[1  (n -1)] can easily be made into a max-heap. The children of the root remain max-heaps,  
31.      * but the new root element may violate the max-heap property. All that is needed to restore  
32.      * the maxheap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap  
33.      * in A[1 (n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size  
34.      * n - 1 down to a heap of size 2. 
35.      * 复杂度： 
36.      * 由之前分析可知，buildMaxHeap复杂度为O(n lg n)，运行一次。 
37.      * maxHeapify的复杂度为O(lg n)，运行n-1次。 
38.      * 综上，复杂度为O(n lg n)。 
39.      */ 
40.     private static void heapSort() { 
41.         int length = input.length; 
42.         //构造max-heap 
43.         buildMaxHeap(input, length);//交换位置 
44.         for (int i = length - 1; i > 0; i--) { 
45.             int temp = input[i]; 
46.             input[i] = input[0]; 
47.             input[0] = temp; 
48.             maxHeapify(input, 1, i); 
49.         } 
50.     } 
51.  
52.     private static void buildMaxHeap(int[] array, int heapSize) { 
53.         for (int i = heapSize / 2; i > 0; i--) { 
54.             maxHeapify(array, i, heapSize); 
55.         } 
56.     } 
57.      
58.     private static void maxHeapify(int[] array, int index, int heapSize) { 
59.         int l = index * 2; 
60.         int r = l + 1; 
61.         int largest; 
62.         //如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值 
63.         if (l <= heapSize && array[l-1] > array[index-1]) { 
64.             largest = l; 
65.         } else { 
66.             largest = index; 
67.         } 
68.         //如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值 
69.         if (r <= heapSize && array[r-1] > array[largest-1]) { 
70.             largest = r; 
71.         } 
72.         //交换位置，并继续递归调用该方法调整位置。 
73.         if (largest != index) { 
74.             int temp = array[index-1]; 
75.             array[index-1] = array[largest-1]; 
76.             array[largest-1] = temp; 
77.             maxHeapify(array, largest, heapSize); 
78.         } 
79.     } 
80.      
81.     private static void printArray() { 
82.         for (int i : input) { 
83.             System.out.print(i + " "); 
84.         } 
85.     } 
86. } 

 

 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/738164，如需转载请自行联系原作者