堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

堆分为大根堆和小根堆，是完全二叉树。

大根堆：任意一个父节点的值大于等于其子节点的值。

小根对：任意一个父节点的值小于等于其子节点的值。

堆排序算法思想：

堆排序使用了堆的数据结构

堆排序算法举例：

下面以数组 a{ 1,5,3,8,7,6 } 进行举例说明，首先初始化堆（利用数组的特点快速定位指定索引的元素）。

首先构建第一个大根堆：

如图所示

首先按照堆的数据结构，初始化堆。

第一步：从最后一个非叶子节点3（叶子节点指的是没有一个孩子的节点）开始，与其左孩子6比较，小于左孩子，换位。最后一个非叶子节点比较完毕。

第二步：找到倒数第二个非叶子节点 5，先于其左孩子比较8，小于左孩子，在于其右孩子7比较，小于右孩子，但左孩子大于右孩子，因此为了保证父节点大于任意子节点，与值较大的左孩子8换位。倒数第二个非叶子节点比较完毕。

第三步：找到倒数第三个非叶子节点1，同第二步。与其左孩子8，右孩子6比较。最终与左孩子8换位。

第四步：因为8和1进行交换，其左子树（方框阴影部分）构成的堆结构被破坏，因此需要递归调用构造堆的函数，重新构造堆。

所有非叶子节点寻找完毕，得到了大根堆：876513

交换大根堆的堆顶元素（第一个元素）与最后一个元素，得到了：376518 （这里的8使用不同颜色进行表示，意在与 8 已经完成了排序，也可以说，二叉树中不再包含元素8，此时堆的长度由6变为5）

构建第二个大根堆：
如图所示

　　同理构造第一个大根堆，只不过此时堆的元素个数由6变成了5，也就是第一趟构造完成后，首尾交换，得到排序好的元素8。此时再次构造堆的时候，堆已经不再包含8这个元素了。

　　此时我们把堆不包含的元素8，用纯红底色圆圈表示。

　　此时，元素6其实已经为叶子节点了（8已经不包含在堆里面了，6没任何孩子）。那么元素3就是最后一个非叶子节点。所以仍然从最后一个非叶子节点开始比较。

　　同第一次构建，我们得到大根堆：756318

　　首尾交换位置（此时的尾为元素1），得到序列：156378

　　第三次构建：78元素已经不在包含在堆中了，元素长度为4，最后一个非叶子节点为3.......

　　以此类推。。直到最后一个非叶子节点为堆顶元素为止。。

实现代码：

 1 #include<stdio.h>
 2 
 3 void swap(int *a, int *b);
 4 //输出数组
 5 void printArr(int a[], int n)
 6 {
 7     for (int i = 0; i < n - 1; i++)
 8     {
 9         printf("%d-", a[i]);
10     }
11     printf("%d", a[n - 1]);
12     printf("
");
13 }
14 
15 //构造大根堆  a数组，length数组长度，i非叶子节点索引值
16 void adjustHeap(int *a, int length, int i)
17 {
18     //左右子节点
19     int l_child = 2 * i + 1;
20     int r_child = 2 * i + 2;
21     //最大值索引
22     int max = i;
23     if (i < length / 2)//i非叶子节点
24     {
25         if (l_child < length && a[max] < a[l_child])//有左孩子并且值小于左孩子
26         {
27             max = l_child;
28         }
29         if (r_child < length && a[max] < a[r_child])//有右孩子并且值小于右孩子
30         {
31             max = r_child;
32         }
33         if (max != i)
34         {
35             swap(&a[i], &a[max]);//交换    
36             printf("构建大根堆中，此时堆元素为%d个：", length);
37             printArr(a, length);
38             adjustHeap(a, length, max);//因为交换了元素，所以有可能破坏子树堆的结构，因此需要递归子树
39         }
40     }
41 }
42 
43 //堆排序  n序列长度
44 void HeapSort1(int *a, int n)
45 {
46     int i = n / 2 - 1;//第一个非叶子节点的索引值
47     int length = n;//未排序堆的元素个数
48 
49     //获取大根堆
50 sign:    for (i; i >= 0; i--)
51 {
52     adjustHeap(a, length, i);
53 }
54         printArr(a, n);
55         if (length > 1)//堆的元素个数大于1
56         {
57             swap(&a[length - 1], &a[0]);//交换堆顶元素和堆得最后一个元素
58             length--;//递减堆的元素
59             i = length / 2 - 1;//修改最后一个非叶子节点的索引值
60             goto sign;//重新返回循环，构建大根堆（本轮循环与上一轮循环，i和length都发生了变化）
61         }
62 
63 }
64 
65 //交换位置
66 void swap(int *a, int *b)
67 {
68     int c = *a;
69     *a = *b;
70     *b = c;
71 }
72 
73 void main()
74 {
75     //堆排序
76     int a[] = { 1,5,3,8,7,6 };
77     HeapSort1(a, 6);
78     getchar();
79 }

代码运行结果：

该运行结果清晰反映了构造堆的每一次排序流程。

常见错误的实现代码：

在百度百科中，看到了C语言实现堆排序的代码，第一眼看的确符合堆的意思，但是仔细品位却发现有着致命问题。

下图为百度百科代码。

首先我用红框框圈住的代码，没有任何必要。

如果一个堆的元素的节点索引是0~n-1，共n个元素，那么任意一个元素 j 的父节点，它的索引值一定是 (j-1)/2，而不用管它是左右孩子节点。

因为这时候，右孩子的 (j-1)/2和 (j-2)/2是完全相等的。比如 0 ，1 ，2 ，3 ，4构成完全二叉树，那么元素4的父节点，(4-1)/2和(4-2)/2相等，。

其次，这真的是堆排序吗？看着似乎是的。

注意该代码：是从最后一个元素开始，依次往前与该节点父节点进行比较。如果父节点小于子节点交换位置，一趟走完，再将堆顶元素和最后一个元素交换位置。看起来是没错的。

但是这不是堆排序，而是一种变形的冒泡排序，双for循环时间复杂度为O(n^2)，。冒泡排序是两个一对的，逐渐往后排，遇到反序交换顺序。。这个是隔了几个元素的两个一对逐渐往后排，遇到反序交换顺序。

如图所示：用该方法序列｛4，3，2，1｝，

先 1、3比得到较大的3

再2、4比得到较大的4

较大的3再和较大的4比得到最大的4...该方法和冒泡几乎无异议，冒泡是：4和3比，换位，4和2比，换位，4和1比，换位，4于是排到最后。。

另外还有各大论坛的一个不规范写法，需要考虑。。如下面代码所示

 1 void HeapSort(int *a, int n)
 2 {
 3     int i = n / 2 - 1;
 4     int j;
 5     //获取大根堆
 6     for (i; i >= 0; i--)
 7     {
 8         adjustHeap(a, n, i);
 9     }
10     //交换首尾元素，并且重新构建堆
11     for (j = n - 1; j > 0; j--)
12     {
13         swap(&a[j], &a[0]);
14         adjustHeap(a, j, 0);
15         printArr(a, n);
16     }
17 }

其他代码都一样，但是堆排序的实现代码有所差别，本代码是先构造出来一个大根堆（完成第9行的时候），然后进行循环替换堆的首尾元素，因为每次调换，都有可能改变堆的结构，所以调用adjustHeap(a, j, 0); 从堆顶开始，从上而下的进行寻找替换（当然每一次替换都可能破坏堆结构，所以用到递归），这种替换方式却违背了堆排序的特点：从最后一个非叶子节点开始，从下往上的原则。

时间复杂度：

初始化建堆过程时间复杂度：O(n)

更改堆元素后重建堆时间复杂度：O(nlogn)

稳定性：

堆排序是一种不稳定的排序算法。