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 }
