题解 | #排序#老实人的堆排序方法

首先讲讲堆的数据结构：堆就是利用完全二叉树的结构建立的一维数组，是顺序存储结构的二叉树，最后一个父节点是dad = len / 2 - 1 两个子结点是son1 = dad * 2 + 1;son2 = dad * 2 + 2

然后说说堆排序的过程：首先是建立最大堆，然后是最大堆调整；我们定义一个MaxHeaplify函数，用于完成以上两个过程，具体的代码+注释如下

class Solution {
public:
 /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  * 将给定数组排序
  * @param arr int整型vector 待排序的数组
  * @return int整型vector
  */
 vector<int> MySort(vector<int>& arr) {
     // write code here
     //1.建立最大堆
     int len = arr.size();
     for (int i = len / 2 - 1; i >= 0; --i) {
         MaxHeaplify(arr, i, len - 1);
     }
     //2.最大堆调整
     for (int i = len - 1; i > 0; --i) {
         swap(arr[0], arr[i]);
         MaxHeaplify(arr, 0, i - 1);
     }
     return arr;
 }
 void MaxHeaplify(vector<int>& arr, int begin, int end) {
     //堆就是利用完全二叉树性质建立的一维数组
     int dad = begin;
     int son = 2 * dad + 1;//第一个子结点
     while (son <= end) {
         if (son + 1 <= end && arr[son + 1] > arr[son]) {
             son++;//将最大的子结点与父节点进行交换
         }
         if (arr[dad] < arr[son]) {
             swap(arr[dad], arr[son]);
             dad = son;
             son = 2 * dad + 1;
         } else {
             return;
         }
     }

 }
};