如果还没有了解过什么是“堆”的话，那可以转移到数据结构专栏有关堆的这一篇文章，二叉树（堆）_KOBE 0824 BRYANT的博客-CSDN博客，这里详细介绍了堆的各种性质，这里就默认大家已经了解“堆”这个数据结构了。
在这里呢我要分享一个效率非常高的排序方法，“堆排序”，它的时间复杂度能够达到惊人的 O(N*logN) ,这比冒泡排序的 O(N^2) 可要高效了不少的，你试想一下，如果N是一百万，那么（N*logN）就是两千万，但是（N^2）可是“一万亿”啊！！！这个差距是什么概念！所以堆排序的效率可要比冒泡排序的效率高得太多了。
那么这个堆排序是怎样的呢？能够达到这种效率，接下来我们就一探究竟。
给定你一个数组，想要进行堆排序首先得先建堆，那如果是要排升序的话，我们需要建小堆还是建大堆呢？？思考5秒钟，你可能会想，这还用说吗？升序肯定是建小堆啊，小堆从上到下不就是升序吗，但是事实真的是这样吗？
你试想一下，如果建小堆，也就意味着你的堆顶的数就是最小的，这个数就不用再动了，但是如果后面的数你需要选出次小的数放到第二个位置，那么你就需要忽略第一个数，以第二个数开始的后面的所有数看作是一个堆，然后调整找到次小的数放到第二个位置，但是以第二个数看作是堆顶的话，那么从第二个数开始的后面的数就不再是一个小堆了，那要选次小的数的话就需要重新建一个小堆，那代价太大了，还不如遍历一遍找到最小的数呢！所以排升序建小堆的话是不可取的。
那么大佬就想，排升序建小堆不行，那我就建大堆，这个大堆的堆顶就是这棵树中最大的，然后和堆的删除走同样的思路，“替换法”。用堆顶的元素和最后一个元素交换，那么堆顶的元素就来到了最后的位置，也就是升序之后的最大的数的位置，并且这里没有影响这棵树本来的性质（各节点之间的关系），然后不把这个最后的数看作是这个大堆里面的数，这时再对堆顶的数（交换上来的数）走一遍向下调整，原来的堆中的次大的数就选出来了，以此类推，就能完成对这个数组的排序了。这真是一个很绝的想法。不愧是大佬。
这里建大堆用向下调整的方法为妙，向下调整建堆的方法请参考博主的数据结构专栏的 二叉树（堆）_KOBE 0824 BRYANT的博客-CSDN博客 这一篇文章，里面有详细过程。
#include <stdio.h> #include <assert.h> void swap(int* a, int* b) { assert(a && b); int tmp = *a; *a = *b; *b = tmp; } void AdjustDown(int* a, int parent, int n) { assert(a); int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child+1] > a[child]) { child++; } if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } int main() { int arr[] = { 123,63,54,36,87,963,1254 }; int sz = sizeof(arr) / sizeof(arr[0]); int parent = 0; //建堆的时间复杂度是: O(N) for (parent = (sz - 1 - 1) / 2; parent >= 0; parent--) { AdjustDown(arr, parent, sz); } //替换法排序的时间复杂度是: O(N*logN) int end = sz; while (end--) { swap(&arr[0], &arr[end]); AdjustDown(arr, 0, end); } //所以堆排序的时间复杂度是:O(N+N*logN)=O(N*logN) int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
在原数组向下调整建大堆的时间复杂度为 O(N)；证明如下：
替换法排序的时间复杂度是: O(N*logN)；所以整体堆排序的时间复杂度为：O(N*logN)；
证明如下：
