Author: bakari Date: 2012.7.30
排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为堆排序。
堆排序是运用二叉树建立的一种排序方式,分为两个阶段,建堆和排序。
看建堆过程:
1 /***********************************************
2 * Author:bakari Date:2012.7.29
3 * 堆排序
4 * 中心算法:关注建堆的过程
5 * i节点的子孩子节点为 2i+1 和 2i+2;
6 ***********************************************/
7 //建立堆的数据结构,此为最大堆
8 void HeapSort::Build_Heap(int current,int last)
9 {
10 int child = 2 * current + 1;
11 int temp = HeapList[current];
12 while(child <= last)
13 {
14
15 if (child < last && HeapList[child] < HeapList[child + 1]) child ++; //找到孩子节点中最大的节点
16 if (temp > HeapList[child]) break; //当前节点大于他的孩子节点说明满足最大堆的特点直接跳出循环
17 else
18 {
19 HeapList[current] = HeapList[child]; //否则将当前节点与孩子节点交换
20 current = child; //将孩子节点替换当前节点
21 child = current * 2 + 1; //继续在孩子节点中找
22 }
23 }
24 HeapList[current] = temp;
25 }
上面有一处小技巧, i 节点 的子孩子节点为 2 i + 1 和 2 i + 2;这个是建堆的关键,上面算法建立的是最大堆,当然也可以建立最小堆,方法类似。
OK,堆一旦建好,就可以进行排序了:
1 void HeapSort::Heap_Sort()
2 {
3 for(int i = (len - 2)/2;i >= 0;i--)
4 Build_Heap(i,len-1);
5 for (int i = len -1;i > 0; i--)
6 {
7 Swap(0,i);
8 Build_Heap(0,i-1);
9 }
10 }