前言
堆排序，顾名思义是一个利用堆来完成排序的一个操作。在之前，小编在[C语言学习系列–＞【关于qsort函数的详解以及它的模拟实现】] 谈到冒泡排序，但是冒泡排序的时间复杂度（O（n2))着实有点高，堆排序的时间复杂度相对低很多，O（log2N）。
堆排序的实现（升序为例）
堆排序不需要我们手搓一个堆的数据结构，因为我们本质上还是在数组上进行操作
堆排序的思想是：
- 对待排序数组构建一个大堆或者小堆
- 将顶端与末尾进行交换，还剩n-1个数
- 将n-1个数再构建成一个大堆或者小堆，这样反复执行，就可以得到一个有序数组
对于大堆、小堆要有清楚的理解，不知道的可以查看小编博客–>堆的实现（C语言版）
堆排序唯一的坑点是：升序需要建大堆，降序建小堆
结论：升序建大堆，降序建小堆
分析：
假设建小堆：0，3，1，5，4，2，9，7，8，6
虽然把最小的元素取出来了，但是一旦把最小元素拿出来，那么剩下的元素又需要重新建堆，这样时间复杂度会提高，缺陷较大。
假设建大堆：9，8，6，7，3，1，2，4，5，0
第一步：将最大的元素，即堆顶的元素和最后一个元素交换
第二步：除了最大的那一个数，对剩下的数进行向下调整算法，得到堆顶是剩下数中的最大元素，然后再和剩下元素=中的最后一个元素进行交换，依次执行
代码
HeapSort.c
# define _CRT_SECURE_NO_WARNINGS void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(int* arr, int parent, int n) { assert(arr); int child = 2 * parent + 1; while (child < n) { if ((child + 1) < n && arr[child + 1] > arr[child]) { child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else break; } } void Heapsort(int* arr, int n) { assert(arr); int i = 0; for (i = (n - 2) / 2; i >= 0; i--) //建堆 { AdjustDown(arr, i, n); } int end = n - 1; while (end) { Swap(&arr[0], &arr[end]); AdjustDown(arr, 0, end); end--; } for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); }
