1 /**
2 *堆排序思路：O(nlogn)
3 * 用最大堆，传入一个数组，先用数组建堆，维护堆的性质
4 * 再把第一个数与堆最后一个数调换，因为第一个数是最大的
5 * 把堆的大小减小一
6 * 再 在堆的大小上维护堆的性质
7 * 重复操作..
8 *
9 *
10 */
11 public class HeapSort
12 {
13 /**
14 *静态变量存放堆的大小
15 */
16 private static int heapsize = 0 ;
17
18 /**
19 *堆排序主方法
20 * 构建最大堆，然后进行堆排序
21 * 堆排序是把最上面的最大的元素放在最下面，然后再维护上面最大堆的性质
22 */
23 public static void heapSort(int[] resouceArr)
24 {
25 //堆的大小
26 heapsize = resouceArr.length - 1 ;
27
28 _buildMaxHeap(resouceArr);
29
30 for( int i = resouceArr.length - 1 ; i >= 0 ; i--)
31 {
32 int temp = resouceArr[0] ;
33 resouceArr[0] = resouceArr[i] ;
34 resouceArr[i] = temp ;
35
36 heapsize = heapsize - 1 ;
37 _maxHeapify( resouceArr, 0 );
38 }
39 }
40
41 /**
42 *构建最大堆
43 * 构建之后还不是有序的，但符合最大堆性质，上面的数一定大于下面的数
44 */
45 private static void _buildMaxHeap(int[] arr)
46 {
47 int length = arr.length - 1 ;
48
49 //从倒数第二排开始维护最大堆性质
50 // 当heapsize为偶数时，heapsize要减一
51 // 当heapsize为奇数时，不变
52 if(length % 2 == 0)
53 {
54 length--;
55 }
56 for( int i = length / 2 ; i >= 0 ; i--)
57 {
58 _maxHeapify(arr , i );
59 }
60 }
61
62 /**
63 *用于维护堆的性质
64 * 树形堆在postion的位置向下维护堆的性质，自postion向下满足最大堆的性质
65 */
66 private static void _maxHeapify(int[] arr,int postion)
67 {
68 //计算postion的左孩子和右孩子
69 postion = postion + 1 ;
70
71 int l = postion * 2 - 1;
72 int r = postion * 2 ;
73 postion = postion - 1 ;
74
75 int largest = maxNumInThreeNum(arr , postion , l , r);
76
77 //如果不满足最大堆性质，则交换值，然后检查树形下方是否满足最大堆性质
78 if(largest <= heapsize)
79 {
80 if( largest != postion)
81 {
82 //交换最大值与父节点值
83 int temp = arr[postion] ;
84 arr[postion] = arr[largest] ;
85 arr[largest] = temp ;
86 //如果子节点变动了，则重新构建已子节点为根的最大堆
87 _maxHeapify(arr , largest);
88
89 }
90 }
91 }
92
93 /**
94 *比较数组中的三个数找出最大值
95 */
96 private static int maxNumInThreeNum(int[] arr ,int a, int b , int c)
97 {
98 int max = a ;
99 //数组长度小于左孩子，最大值为本身
100 if(heapsize < b)
101 {
102 max = a ;
103 }
104 else if(heapsize >=b && heapsize < c)
105 {
106 if(arr[a] < arr[b])
107 {
108 max = b ;
109 }
110 }
111 else
112 {
113 if(arr[a] > arr[b])
114 {
115 max = a ;
116 }
117 else
118 {
119 max = b ;
120 }
121 if(arr[max] < arr[c])
122 {
123 max = c ;
124 }
125 }
126 return max ;
127 }
128 }
