堆排序(五)
其中，N为数组下标索引值，如数组中第1个数对应的N为0。
70 *
71 * 参数说明：
72 * a -- 待排序的数组
73 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
74 * end -- 截至范围(一般为数组中最后一个元素的索引)
75 */
76 public static void minHeapDown(int[] a, int start, int end) {
77 int c = start; // 当前(current)节点的位置
78 int l = 2*c + 1; // 左(left)孩子的位置
79 int tmp = a[c]; // 当前(current)节点的大小
80
81 for (; l <= end; c=l,l=2*l+1) {
82 // "l"是左孩子，"l+1"是右孩子
83 if ( l < end && a[l] > a[l+1])
84 l++; // 左右两孩子中选择较小者
85 if (tmp <= a[l])
86 break; // 调整结束
87 else { // 交换值
88 a[c] = a[l];
89 a[l]= tmp;
90 }
91 }
92 }
93
94 /*
95 * 堆排序(从大到小)
96 *
97 * 参数说明：
98 * a -- 待排序的数组
99 * n -- 数组的长度
100 */
101 public static void heapSortDesc(int[] a, int n) {
102 int i,tmp;
103
104 // 从(n/2-1) --> 0逐次遍历每。遍历之后，得到的数组实际上是一个最小堆。
105 for (i = n / 2 - 1; i >= 0; i--)
107
108 // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
109 for (i = n - 1; i > 0; i--) {
110 // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。
111 tmp = a[0];
112 a[0] = a[i];
113 a[i] = tmp;
114 // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。
115 // 即，保证a[i-1]是a[0...i-1]中的最小值。
116 minHeapDown(a, 0, i-1);
117 }
118 }
119
120 public static void main(String[] args) {
121 int i;
122 int a[] = {20,30,90,40,70,110,60,10,100,50,80};
123
124 System.out.printf("before sort:");
125 for (i=0; i
126 System.out.printf("%d ", a[i]);
127 System.out.printf("\n");
128
129 heapSortAsc(a, a.length); // 升序排列
130 //heapSortDesc(a, a.length); // 降序排列
131
132 System.out.printf("after sort:");
133 for (i=0; i
134 System.out.printf("%d ", a[i]);
135 System.out.printf("\n");
136 }
137 }
它们的输出结果：
before sort:20 30 90 40 70 110 60 10 100 50 80
after sort:10 20 30 40 50 60 70 80 90 100 110