【算法导论】堆排序

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

堆排序的原理：

构建并且维持一个最大堆，然后交换堆的第一个和最后一个元素，每次交换后最大的元素都被移到最后。然后堆的规模减一，继续交换，直到进行到第二个元素。这时排序完成

图解：（图片来源于http://blog.163.com/zhoumhan_0351/blog/static/399542272009918112712205/）

技术分享

算法分析：

维持一个最大堆的复杂度为?（lgN），建立一个最大堆的复杂度为?（N），Heap_sort过程调用了一次Build_Heap, n-1次Max_Heap。总的复杂度为?（N‘l‘g‘N）

C++源代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 //维护堆的性质，使堆都能维持为最大堆 
 7 void Max_Heap(int *a, int i, int size)
 8 {
 9     int l = 2 * i;     //得到左孩子 
10     int r = 2 * i + 1; //得到又孩子 
11     int max;
12 
13     if (l <= size && a[l] > a[i]){
14         max = l;
15     }
16     else
17         max = i;
18     if (r <= size && a[r] > a[max]){
19         max = r;
20     }
21     if (max != i){
22         swap(a[i], a[max]);
23         Max_Heap(a, max, size);
24     }
25 }
26 
27 //建立一个最大堆  
28 void HeapBUild(int *a, int size){
29     int i;
30     for (i = size / 2; i >= 1; i--){
31         Max_Heap(a, i, size);
32     }
33 }
34 
35 //堆排序 
36 void HeapSort(int *a, int size){
37     int i;
38     HeapBUild(a, size);      //先建立一个最大堆 
39     for (i = size; i >= 1; i--){
40         swap(a[1], a[i]);    //交换第一个和最后一个元素 
41         Max_Heap(a, 1, i - 1);  // size-1，递归 
42     }
43 }
44 
45 int main(int argc, char *argv[]){
46     int i;
47     int a[] = { 0, 16, 20, 3, 11, 17, 8 };
48     int size = 7;
49     HeapSort(a, size);
50     for (i = 1; i <= size; i++)
51         cout << a[i - 1] << " ";
52     return 0;
53 }