堆排序

浏览数：23 / 时间：2015年06月08日

堆排序

 1 // 将待排序的最后一个元素current插入大根堆中
 2 void insert_heap(int *arr, int current, int low, int high)
 3 {
 4     //记录low的孩子结点中较大元素的下标，初始化为左孩子
 5     int large = 2*low + 1;
 6     while(large <= high)
 7     {
 8         //右孩子较大
 9         if(large < high && arr[large] < arr[large+1])
10             large++;
11         //当前元素大于所有孩子
12         if(current >= arr[large])
13             break;
14         else//当前元素小于左右孩子中较大的一个
15         {
16             arr[low] = arr[large];
17             low = large;
18             large = 2*low + 1;
19         }
20     }
21     //将目标元素插入合适的位置
22     arr[low] = current;
23 }
24 
25 //建堆
26 void build_heap(int *arr, int n)
27 {
28     int low, current;
29     //从最后一个非叶结点开始
30     for(low = n/2 - 1; low >= 0; low--)
31     {
32         current = arr[low];
33         insert_heap(arr,current,low,n-1);
34     }
35 }
36 
37 //堆排序，从后往前，每次将堆头最大的元素放到堆尾，同时将堆尾元素插入到堆中
38 void hearSort(int *arr, int n)
39 {
40     int current;//暂存待插入的元素
41     int last_unsorted;//未排序的最后一个元素
42     build_heap(arr,n);//建堆
43 
44     for(last_unsorted = n-1; last_unsorted > 0; last_unsorted--)
45     {
46         current = arr[last_unsorted];//暂存堆尾元素
47         arr[last_unsorted] = arr[0];//堆头元素放在堆尾
48         insert_heap(arr,current,0,last_unsorted-1);//未排序的堆尾元素插入堆
49     }
50 }