经典排序之 堆排序

 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 }

 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 }