2. 堆排序『较难理解的排序』

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。这个堆是一个近似完全二叉树的结构，并且还是个大顶堆，排序也是根据这个大顶堆来进行的。

为什么说 堆排序 比较难理解呢？答：主要原因是 有些人 可能没学过 二叉树，更不知道什么是 堆，更没学过 模拟数组的思想。也就是说 他在没有这些 前提知识点的情况下，怎么可能 好的理解 堆排序呢。更何况 堆排序 调整堆那里的实现，还 用到了 我们最头大的递归。而且 整体的排序思路，一旦 讲师 没有讲清楚，可能 就 是一知半解的。

1.1 算法描述

• 用数组模拟二叉树结构，使得每个根节点的左右节点 对应下标为 left = 2k + 1、right = 2k + 2。
• 将这个二叉树 初始化为 大顶堆，这里要 用到 递归的操作。思想是 从最后的那个子树开始，往前 把每个 子树 都变为大顶堆！当然还会有 后效性问题（即 当我们 调整了节点顺序后，被交换的这个节点 作为根节点的那个子树 是否还是 大顶堆呢？？），所以 我们 这里 就需要 递归，然后 去 处理 该节点下面的所有子树。
• 由于 整个二叉树的根节点 是 最大的值，所以我们 可以 把 这个节点 和 最后 一个节点 进行交换。即 在 1 ~ n 个节点的范围内，这个 根节点 是 最大值，我们将它 放在 最后。然后 我们再把 1 ~ n – 1 个节点范围的二叉树（排除 最后一个节点）让其再次变为 大顶堆，然后 再去 进行 上述的操作，把倒数第二个 最大值 放到了 倒数第二的位置。以此类推，当我们 处理到只剩下 第一个节点的二叉树的时候，则整体 有序！！

---

1.2 动图演示

---

1.3 代码实现

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

vector<int> arr = {
    91,60,96,13,35,65,46,65,10,30,20,31,77,81,22};

int len;

void swapF(int k){
    // 对以 k 为 根节点 的子树 进行 探索 和 调整
  int left = 2 * k + 1;
  int right = 2 * k + 2;
  
  int father = k;// 待更新的 根节点，可能 根节点 需要 调整更新
  
  if(left < len && arr[left] > arr[father]){
    
    father = left;// 左节点 比 根节点 大，所以 左节点的下标 保存到
    // father 里，提前 预备 根节点的位置
  }
  
  if(right < len && arr[right] > arr[father]){
    
    father = right;// 若 最大的节点 是 右节点，那么 father = right
  }
  
  if(father != k){
    // 如果 该子树进行了 调整,即 根节点 发生变化
    // 那么就要 处理 后效性问题
    swap(arr[father],arr[k]);// 先将 这颗子树进行调整
    swapF(father);// 然后 来 看下 被我们交换的节点的位置 数据发生了
    // 变化后，是否 还 保持 着大顶堆的 性质
  }
}

void init(){
    
  len = arr.size();
  for(int i = floor(len / 2);i >= 0; i--){
    // 从 最后一个 子树开始
    swapF(i);
  }
}

void heapSort(){
    
  init();
  for(int i = len - 1;i > 0;--i){
    
    // 进行 排序，把每一个 区间内 最大的值，都 放到 该放的位置
    swap(arr[i],arr[0]);
    len--;
    swapF(0);
  }
}

int main(void){
    
  heapSort();
  for(auto x : arr){
    
    cout << x << " ";
  }
  return 0;
}

堆排序 分为两个部分：堆的调整 + 堆的排序。

时间复杂度：O(n) + O(nlogn) = O(nlogn)

空间复杂度：O(1)