题解 | #排序#

#include <vector>
class Solution {

public:

    int len = 0;    // 记录数组长度

    void heapAdjust(vector<int> &arr, int k, int len){
        // 堆排序，将以k为根的节点进行调整,选出最大的堆
        // tmp用来记录最大值，arr[k]记录每次遍历的最大值，最后会更新为当前子树的最大值
        int tmp = arr[k];
        // vector索引从0开始，初始值应该+1,索引值的选择很重要哈
        for(int i = 2*k + 1;i<len;i = 2*i +1){
            // 保证不越界，并找到较大的节点
            if(arr[i]<arr[i+1] && i+1 <len)
                i++;
            // 已经满足最大的值，在根节点，结束循环
            if(tmp >= arr[i]){
                break;
            }
            // 继续调整
            arr[k] = arr[i];
            k = i;
        }
        // 循环结束，arr[k]为子树中的最大节点
        arr[k] = tmp;
    }

    vector<int> MySort(vector<int>& arr) {
        // write code here
        len = arr.size();
        // 一直调整到根节点
        for(int i = len/2 - 1;i>=0;i--)
            // 用于保存子树，对子树进行循环调整
            heapAdjust(arr, i, len);
        for(int i=len-1;i>0;i--){
            swap(arr[0], arr[i]);
            // 调整堆以保持最大堆性质
            heapAdjust(arr, 0, i);
        }
    return arr;
    }
};