终于到了堆排序了，不过在写堆排序之前得先看看选择排序，毕竟堆排序的根本思想还是源于选择排序
选择排序：
i<--1 ~ length - 2
对元素a[i]，从i + 1 ~ length - 1中选择出比i小的那个最小的数(假设为a[j])，然后交换a[i]与a[j]的值，然后对i进行遍历。
思想就是这么简单，很明显选择排序时间复杂度为O(n2)。
1 /********************************
2 * high为要排序数组的最后一个元素的下一个地址
3 ********************************/
4 void SimpleSort(int a[], int low, int high)
5 {
6 int i, j;
7 int value, index;
8
9 for (i = low; i < high; ++i)
10 {
11 value = a[i];
12 index = i;
13
14 for (j = i + 1; j <= high; ++j)
15 {
16 if (a[j] < value)
17 {
18 value = a[j];
19 index = j;
20 }
21 }
22
23 if (index != i)
24 {
25 EXCHANGE(a[i], a[index]);
26 }
27 }
28 }
EXCHANGE就是一个简单的交换元素值的函数，可以写成内联函数的形式：
1 inline void EXCHANGE(int &a, int &b)
2 {
3 a = a ^ b;
4 b = a ^ b;
5 a = a ^ b;
6 }
比较简单，不再赘述。
下面还是看堆排序吧，其实我觉得它应该和快排一样有魅力：
先是在一个普通数组中建堆；然后再在建好的堆的基础上进行堆排序。
核心的代码应该是下面的这个函数：
1 void max_heapify(int a[], int head, int tail)
2 {
3 int largest;
4 int left = LEFT(head);
5 int right = RIGHT(head);
6
7 if (left < tail && a[left] > a[head])
8 {
9 largest = left;
10 }
11 else
12 {
13 largest = head;
14 }
15
16 if (right < tail && a[right] > a[largest])
17 {
18 largest = right;
19 }
20
21 if (largest != head)
22 {
23 EXCHANGE(a[head], a[largest]);
24 max_heapify(a, largest, tail);
25 }
26 }
这个函数的功能就是调整堆结构以使元素a[head]比它左右孩子都大。这里有个假设：就是假定a[head]的左右孩子都已经是建好的堆了。
这个假设很重要，这就使得我们再建堆的时候需要由叶子节点往上建，反应到数组上就是由a[(tail - 1) / 2]开始往前。为什么不从a[tail - 1]开始往前建呢？那是因为自a[(tail - 1) / 2]开始到a[tail - 1]都是叶子节点，这些节点已经是一个只包含一个节点的堆了，因此只需要从a[(tail - 1) / 2]开始就可以了。看如下代码：
1 void build_max_heap(int a[], int tail)
2 {
3 int i;
4
5 for (i = (tail - 1) / 2; i > 0; --i)
6 {
7 max_heapify(a, i, tail);
8 }
9 }
最后才是堆排序的代码：
1 void heap_sort(int a[], int tail)
2 {
3 int i;
4 build_max_heap(a, tail);
5
6 for (i = tail - 1; i > 1; --i)
7 {
8 EXCHANGE(a[1], a[i]);
9 max_heapify(a, 1, i);
10 }
11 }
它首先调用函数build_max_heap()函数建堆，需要耗费O(nlgn)时间，然后是根据已经建立好的堆进行排序的过程了：这个过程说起来也比较简单，每次都是让堆的顶元素与堆的最后一个元素互换，然后再对堆顶进行调整，即调用max_heapify()函数。这样，当循环结束时堆排序便完成了，实践耗费为O(nlgn)。因此总的说来堆排序时间复杂度为O(nlgn)的。
posted on 2011-05-01 00:41
myjfm 阅读(266)
评论(0) 编辑 收藏 引用 所属分类:
杂