题解 | #排序#

//堆排序  时间O(n log n) 空间O(1) 不稳定
#include <any>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    void heapSort(vector<int>& nums,int heapsize){
        //调整为小根堆
        for(int i=heapsize/2-1;i>=0;i--){
            heapify_down(nums, heapsize, i);
        }
        //输出
        for(int i=heapsize-1;i>0;i--){
            swap(nums[0],nums[i]);
            heapsize--;
            //先减小堆数量  再调整堆
            heapify_down(nums, heapsize, 0);
        }
    }

    void heapify_down(vector<int>& nums,int heapsize,int i){
        int largest=i;
        int left=2*i+1;
        int right=2*i+2;
        if(left<heapsize&&nums[left]>nums[largest]) largest=left;
        if(right<heapsize&&nums[right]>nums[largest]) largest=right;
        if(largest!=i){
            swap(nums[largest],nums[i]);
            heapify_down(nums,heapsize,largest);
        }
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        heapSort(arr, arr.size());
        return arr;
    }
};