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