堆排序(四)
// 当前(current)节点的位置
84 int l = 2*c + 1; // 左(left)孩子的位置
85 int tmp = a[c]; // 当前(current)节点的大小
86 for (; l <= end; c=l,l=2*l+1)
87 {
88 // "l"是左孩子，"l+1"是右孩子
89 if ( l < end && a[l] > a[l+1])
90 l++; // 左右两孩子中选择较小者
91 if (tmp <= a[l])
92 break; // 调整结束
93 else // 交换值
94 {
95 a[c] = a[l];
96 a[l]= tmp;
97 }
98 }
99 }
100
101 /*
102 * 堆排序(从大到小)
103 *
104 * 参数说明：
105 * a -- 待排序的数组
106 * n -- 数组的长度
107 */
108 void heapSortDesc(int* a, int n)
109 {
110 int i,tmp;
111
112 // 从(n/2-1) --> 0逐次遍历每。遍历之后，得到的数组实际上是一个最小堆。
113 for (i = n / 2 - 1; i >= 0; i--)
114 minHeapDown(a, i, n-1);
115
116 // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
117 for (i = n - 1; i > 0; i--)
118 {
119 // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。
120 tmp = a[0];
121 a[0] = a[i];
122 a[i] = tmp;
123 // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。
124 // 即，保证a[i-1]是a[0...i-1]中的最小值。
125 minHeapDown(a, 0, i-1);
126 }
127 }
128
129 int main()
130 {
131 int i;
132 int a[] = {20,30,90,40,70,110,60,10,100,50,80};
133 int ilen = (sizeof(a)) / (sizeof(a[0]));
134
135 cout << "before sort:";
136 for (i=0; i
137 cout << a[i] << " ";
138 cout << endl;
139
140 heapSortAsc(a, ilen); // 升序排列
141 //heapSortDesc(a, ilen); // 降序排列
142
143 cout << "after sort:";
144 for (i=0; i
145 cout << a[i] << " ";
146 cout << endl;
147
148 return 0;
149 }
复制代码
堆排序Java实现
实现代码(HeapSort.java)
复制代码
1 /**
2 * 堆排序：Java
3 *
4 * @author skywang
5 * @date 2014/03/11
6 */
7
8 public class HeapSort {
9
10 /*
11 * (最大)堆的向下调整算法
12 *
13 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
14 * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
15 *
16 * 参数说明：
17 * a -- 待排序的数组
18 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
19 * end -- 截至范围(一般为数组中最后一个元素的索引)
20 */
21 public static void maxHeapDown(int[] a, int start, int end) {
22 int c = start; // 当前(current)节点的位置
23 int l = 2*c + 1; // 左(left)孩子的位置
24 int tmp = a[c]; // 当前(current)节点的大小
25
26 for (; l <= end; c=l,l=2*l+1) {
27 // "l"是左孩子，"l+1"是右孩子
28 if ( l < end && a[l] < a[l+1])
29 l++; // 左右两孩子中选择较大者，即m_heap[l+1]
30 if (tmp >= a[l])
31 break; // 调整结束
32 else { // 交换值
33 a[c] = a[l];
34 a[l]= tmp;
35 }
36 }
37 }
38
39 /*
40 * 堆排序(从小到大)
41 *
42 * 参数说明：
43 * a -- 待排序的数组
44 * n -- 数组的长度
45 */
46 public static void heapSortAsc(int[] a, int n) {
47 int i,tmp;
48
49 // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
50 for (i = n / 2 - 1; i >= 0; i--)
51 maxHeapDown(a, i, n-1);
52
53 // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
54 for (i = n - 1; i > 0; i--) {
55 // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
56 tmp = a[0];
57 a[0] = a[i];
58 a[i] = tmp;
59 // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
60 // 即，保证a[i-1]是a[0...i-1]中的最大值。
61 maxHeapDown(a, 0, i-1);
62 }
63 }
64
65 /*
66 * (最小)堆的向下调整算法
67 *
68 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
69 *