排序算法 —— 堆排序

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;
}