目录

1. 堆排序的基础知识

1.1 大顶堆&&小顶堆 

1.2 向下调整算法

1.3 物理结构与逻辑结构的关系

2. 堆排序详解

2.1 堆排序整体思路 

2.2 思路详解

2.2.1 建堆

2.2.2 大堆or小堆

2.2.3 输出数据

3. 时间复杂度分析

4. 完整代码

 5. 彩蛋

1. 堆排序的基础知识

堆排序（Heap Sort）就是对直接选择排序的一种改进。此话怎讲呢？直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的，但是在选出最大或者最小的数后，并没有对原来的序列进行改变，这使得下一次选数时还需要对全部数据进行比较，效率大大降低。

堆排序算法是Floyd和Williams在1964年共同发明的，同时他们发明了“堆”这种数据结构。

1.1 大顶堆&&小顶堆 

对于待排序的数组元素，我们可以将它的逻辑结构看成二叉树。满足某种条件的这种逻辑结构就是堆啦。

讯享网

显然，这是一棵完全二叉树。那么某种条件是啥呢？

堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为：大顶堆（大堆）；或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆（小堆）。 

1.2 向下调整算法

使用该算法的前提是该节点的左右子树要么都是大堆，要么都是小堆。

该算法就是将该节点与左右子树的节点进行比较，重新构建成一个大堆或者小堆。

1.3 物理结构与逻辑结构的关系

假设我们有了一个待排序的数组，并且构建好了他的逻辑结构，怎么能通过孩子找到双亲，或者通过双亲找到左右孩子呢？

先看公式： parent = (child - 1) / 2 ;

                   leftchild = parent * 2 + 1 ;

                   rightchild = parent * 2 + 2 ;

                   rightchild = leftchild + 1；

有了这个公式，左孩子，右孩子，双亲的下标知道一个就可以求其他两个啦！

2. 堆排序详解

是的，堆排序就是通过建堆的方式来弥补直接选择排序的缺陷滴。 

2.1 堆排序整体思路 

1）：给出待排序的数组，咱们脑补一个逻辑结构，然后将该逻辑结构整体调整为大堆或者小堆。 

2）： 留个问题：升序是构建大堆还是小堆呢？提示：请参考直接选择排序的缺陷，以及堆排序如何弥补该缺陷的。搞清楚这个问题后排序即可。

3）：打印输出数据。

2.2 思路详解

2.2.1 建堆

以大堆为例哈：既然前面都铺垫了向下调整算法，你们肯定猜到了是通过该算法来建堆啦。

注意该算法的使用前提：要求左右子树都是大堆。怎么办呢？聪明如你们，我们从逻辑结构的后面往前面用该算法不就行啦！！

/// <summary> /// 交换数组元素 /// </summary> /// <param name="pa">被交换的元素a</param> /// <param name="pb">被交换的元素b</param> void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } /// <summary> /// 对逻辑结构进行向下调整，构建大堆 /// </summary> /// <param name="arr">数组首元素地址</param> /// <param name="n">数组大小</param> /// <param name="root">要调整的节点</param> void AdjustDown(int* arr, int n, int root) { //双亲的下标 int parent = root; //较大孩子的下标，默认为左孩子 int child = parent * 2 + 1; //如果孩子的下标不越界，进入循环 while (child < n) { //如果右孩子存在（下标没越界），并且右孩子大于左孩子，更新child if (child + 1 < n && arr[child + 1] > arr[child]) { child = child + 1; } //如果较大的孩子大于双亲，交换 if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); //改变parent的下标如果满足条件继续向下调整 parent = child; child = parent * 2 + 1; } //如果较大的孩子不大于双亲，root节点的大堆构建完毕 else { break; } } } /// <summary> /// 堆排序函数 /// </summary> /// <param name="arr">数组首元素地址</param> /// <param name="n">数组大小</param> void HeapSort(int* arr, int n) { //循环从后面往前面对需要的数组元素使用向下调整算法 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, n, i); } }

2.2.2 大堆or小堆

以升序为例：建大堆完成后就是这个样子啦：9, 8, 6, 7, 3, 1, 2, 4, 5, 0 ；

                      建小堆完成后就是这个样子：0, 3, 1, 5, 4, 2, 9, 7, 8, 6 ；

建小堆只需要将AdjustDown里面的两个if语句的大于改成小于。

2.2.3 输出数据

这部分比较简单，不多分析。 

3. 时间复杂度分析

堆排序的时间复杂度分析，应该是排序算法中最复杂的，需要具备高中的基础知识！！！！

4. 完整代码

讯享网#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> /// <summary> /// 交换数组元素 /// </summary> /// <param name="pa">被交换的元素a</param> /// <param name="pb">被交换的元素b</param> void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } /// <summary> /// 对逻辑结构进行向下调整，构建大堆 /// </summary> /// <param name="arr">数组首元素地址</param> /// <param name="n">数组大小</param> /// <param name="root">要调整的节点</param> void AdjustDown(int* arr, int n, int root) { //双亲的下标 int parent = root; //较大孩子的下标，默认为左孩子 int child = parent * 2 + 1; //如果孩子的下标不越界，进入循环 while (child < n) { //如果右孩子存在（下标没越界），并且右孩子大于左孩子，更新child if (child + 1 < n && arr[child + 1] > arr[child]) { child = child + 1; } //如果较大的孩子大于双亲，交换 if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); //改变parent的下标如果满足条件继续向下调整 parent = child; child = parent * 2 + 1; } //如果较大的孩子不大于双亲，root节点的大堆构建完毕 else { break; } } } /// <summary> /// 打印数组元素 /// </summary> /// <param name="arr">数组首元素地址</param> /// <param name="n">数组元素个数</param> void PrintArray(int* arr, int n) { int i = 0; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } } /// <summary> /// 堆排序函数 /// </summary> /// <param name="arr">数组首元素地址</param> /// <param name="n">数组大小</param> void HeapSort(int* arr, int n) { //循环从后面往前面对需要的数组元素使用向下调整算法 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, n, i); } //用来控制向下调整时的数组元素个数 int end = n - 1; while (end > 0) { //交换元素，获得最大值 Swap(&arr[0], &arr[end]); //进行向下调整, 因为开始end为n-1嘛 AdjustDown(arr, end, 0); //去除较大值 --end; } } int main() { //待排序的数组 int arr[] = { 6,4,2,8,3,1,9,7,5,0 }; //调用主体函数 HeapSort(arr, sizeof(arr) / sizeof(arr[0])); //打印数据 PrintArray(arr, sizeof(arr) / sizeof(arr[0])); return 0; }

 5. 彩蛋

为了直观的比较几大排序算法的快慢，我们可以设计程序以毫秒数来量化排序的快慢。