1.题目介绍

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

2.题解

2.1 堆排序

思路

题目给了我们一个vector数组，要使用堆排序，我们首先要创建一个大根堆，再在这个大根堆的基础上对数组进行排序
一.创建大根堆
1.利用好完全二叉树的性质，对于一个序号为i的节点，其父节点为 i/2, 左子结点为 2i, 右子节点为 2i+1, 但注意！！！这只是针对索引从1开始的情况
这里我们数组索引从0开始，父节点为 i/2, 左子结点为 2i+1, 右子节点为 2i+2；
对应int lson = (i << 1) + 1, rson = (i << 1) + 2;

2.创建大根堆采用自下而上的方式（有点类似递归的思想），先将节点i的左右子树都建立为大根堆，也就是两边子树最大的值刚好为节点i的左右子节点，再来跟节点i进行判断，将其中大的换上来或者保留原值即可。

3.创建大根堆时，选择从len/2开始？这是因为叶子结点在创建大根堆时先行跳过，直接从叶子结点上一层开始进行调整（叶子结点无左右子节点，无法比较）
对应for(int i = len / 2; i >= 0; i--){...}

4.注意当第一次判断中左子结点不存在或者小于根节点时，large = i;

5.注意：这里 i = large; 配合 for(; (i << 1) + 1 <= len;){} 使得当完成一次节点交换后，我们重新构建子大根堆。因为我们将较小值换到子节点，可能破坏下方的大根堆，所以需要检查！！！
if (large != i){ swap(nums[i], nums[large]); i = large; }

二.堆排序
每次将大根堆的根节点，也就是最上方的节点换到最后一个节点固定，这样最后一个最大数便已经确定
之后再调整剩余元素的大根堆，再将调整后的根节点换到倒数第二个节点固定，依次这样进行，每次将最大的节点换到待排序数组末尾即可。

代码

class Solution {
    /* 调整以i为根节点的大根堆 */
    void maxHeapify(vector<int>&nums, int i, int len){
        for(; (i << 1) + 1 <= len;){
            int lson = (i << 1) + 1, rson = (i << 1) + 2;
            int large;
            if (lson <= len && nums[lson] > nums[i]) large = lson;
            else large = i;
            if (rson <= len && nums[rson] > nums[large]) large = rson;
            if (large != i){
                swap(nums[i], nums[large]);
                i = large;
            }
            else break;
        }
    }

    /* 创建大根堆,自下向上 */
    void buildMaxHeap(vector<int>&nums, int len){
        for(int i = len / 2; i >= 0; i--){
            maxHeapify(nums, i, len);
        }
    }

    /* 大根堆排序*/
    void heapSort(vector<int>&nums){
        int len = (int)nums.size() - 1;
        buildMaxHeap(nums, len);
        for(int i = len; i >= 1; i--){
            swap(nums[0], nums[i]);
            len--;
            maxHeapify(nums, 0, len);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
};