虽然在之前的【树】章节，我们已经学习了堆排序。但是这里我们任然要回顾并且补充一些堆排序算法点。
HeapSort堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。
- 注意的是排升序要建大堆，排降序建小堆。
直接选择排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
整体思路
- 向下调整算法AdjustDown
- 建堆（两种方式，主要以向下调整为重点❗）
- 堆排序
- 建大堆：升序
- 建小堆：降序
- 1：交换头尾
- 2：向下调整（除去最后一个元素&&最后一个元素已经排好序了）
- 3：循环重复上述过程，直到全部调整完成
图解分析
【1】向下调整算法
//向下调整 void Adjustdown(int * a, int size, int parent) { //假设法 int child = parent * 2 + 1; while (child < size ) { if (child + 1 < size && a[child + 1] < a[child])//注意❗ { child++; } //比较 if (a[child] < a[parent]) { //交换 Swap(&a[child], &a[parent]); parent = child; child = child * 2 + 1; } else//>= { break; } } }
【2】向下调整建堆
//向下调整建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, size, i); }
【3】排序
void HeapSort(int* a, int size) { //1.向下调整建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { //向下调整算法 Adjustdown(a, size, i); } //2.排序 while (size) { //交换 Swap(&a[0], &a[size - 1]); //向下调整(除去已经排序好的元素） Adjustdown(a, size - 1, 0); //到达下一个交换的位置 size--; } }
时间复杂度
- 建队的时间复杂度：O(N）/ O（N*logN）
- 高度次：logN
- 交换+向下调整（调整高度次）：O（logN*N）=O（N*logN）
- 堆排序的时间复杂度：O（N）+O（N*logN）=O（N*logN）
- 堆排序的时间复杂度：O（N*logN）
🙂感谢大家的阅读，若有错误和不足，欢迎指正。下篇快速排序算法。
