目录
1.堆排序的思想
2.堆排序的实现
建堆
向上调整建堆
向下调整建堆
选数
堆排序实现代码
3.堆排序总结
1.堆排序的思想
堆排序是利用堆这种数据结构设计的排序算法，更准确的说，是利用堆的删除操作所设计的一种排序算法。
比如：删除堆顶元素的时候，我们使用的是替换法删除，也就是将堆顶元素和数组末尾的元素交换，每次选择的堆顶元素是堆中当前的最大or最小元素。相当于每次都能在待排序序列中选出一个最值，从后往前填入数组中的一个正确位置。
- 如果是大堆，每次选出的数据就是当前堆中最大的元素，从数组后面往前填入数组，排出来的数据是升序的。
- 如果是小堆，每次选出的数据就是当前堆中最小的元素，从数组后面往前填入数组，排出来的数据是降序的。
所以，如果我们想排升序，建堆的时候，应该建立大堆；如果我们想排降序，建堆的时候，应该建立小堆。
2.堆排序的实现
堆排序的实现主要分为两步：建堆和选数。
建堆
堆排序是在堆这种数据结构的基础上进行的，所以想要进行堆排序必须先建堆。建堆方式分为两种，一种是向上调整建堆，一种是向下调整建堆。
向上调整建堆
向上调整的前提是当前调整的数据 前面的数据构成堆。所以，向上调整建堆的顺序应该从上往下、从左往右依次进行向上调整。一个数据通过向上调整建堆最多调整树的高度减1次，也就是logN，一共N个数据，所以向上调整建堆的时间复杂度是O(N*logN)。
向下调整建堆
向下调整的前提是左右子树都是堆，也就是当前数据后面的数据是堆。所以，向下调整建堆的顺序应该从右往左、从下往上依次进行。因为，叶子结点没有孩子，所以应该从倒数第一个非叶子结点开始进行向下调整。
向下调整建堆代码：
void AdjustDown(int* a, int n, int parent)
{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;}}
}向下调整建堆时间复杂度分析：
向下调整建堆的时间复杂度为O(N)，要优于向上调整建堆，所以我们采用向下调整建堆。
选数
所谓选数，就是每次都选择堆顶元素，然后将堆顶元素和数组未排序空间的最后一个元素交换，每次选择的堆顶元素是堆中当前的最大or最小元素。相当于每次都能在待排序序列中选出一个最值，从后往前填入数组中的一个正确位置。
流程图如下所示：
堆排序实现代码
#include <stdio.h>void swap(int* p1, int *p2)
{int t = *p1;*p1 = *p2;*p2 = t;
}void AdjustDown(int* a, int n, int parent)
{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;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆// O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int nums[] = {5,4,8,9,6,3,2,1,7,0};HeapSort(nums,10);int i = 0;while(i < sizeof(nums) / sizeof(int)){printf("%d ",nums[i]);i++;}return 0;
}3.堆排序总结
- 时间复杂度：O(N*logN)。采用向下调整建堆，时间复杂度为O(N)；逐元素进行向下调整，时间复杂度为log(N)；所以总的时间复杂度为O(N*logN)。
- 空间复杂度：O(1)。并没有开辟额外的空间，时间复杂度为O(1)。
- 稳定性：不稳定，如图所示。
