912. 排序数组（排序练手 ）

给你一个整数数组 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]

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

class MergeSort {
public:
   
    vector<int> temp;
    MergeSort(int n) {
        temp = vector<int>(n,0);
    }
    void merge(vector<int>& nums, int low , int mid, int high ) {
        for(int i = low ; i <= high;i++) {
            temp[i] = nums[i];
        }
        int i = low;
        int j = mid+1;
        for(int pp = low; pp <= high;pp++) {
            if (i<=mid && j <=high) {
                nums[pp] = temp[i] > temp[j]? temp[i++]: temp[j++];
            } else if (i<=mid) {
                nums[pp] = temp[i++];
            } else if (j<=high) {
                nums[pp] = temp[j++];
            }
        }
    }
    //二叉树后续遍历，左边排好，右边排好，然后 merge
    void merge_sort(vector<int>& nums, int low, int high ) {
        if (low >= high) return;
        int mid = low + (high - low )/2;
        merge_sort(nums,low,mid);
        merge_sort(nums,mid+1,high);
        merge(nums,low,mid,high);
    } 
};


class QuickSort {
public:
    int partation(vector<int>& nums, int low , int high ) {
        // 找到一个分界点，左边的小于 key, 右边的大于 key
        int key = nums[low];
        int i = low+1;
        int j = high;
        while(i<=j) {
            if (nums[i] < key && key < nums[j]) {
                swap(nums[i++],nums[j--]);
            }
            if (nums[i]>=key) {
                i++;
            }
            if (key >=nums[j]) {
                j--;
            }
        }
        swap (nums[low],nums[j]);
        return j;
    }
    //二叉树前序遍历，先将 key 放到合适的位置，保证左边的小于 key, 右边的大于 key
    void quick_sort(vector<int>& nums, int low, int high ) {
        if (low >= high) return;
        int p = partation(nums,low,high);
        quick_sort(nums,low,p-1);
        quick_sort(nums,p+1,high);
    } 
};

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //MergeSort msort = MergeSort(nums.size());
        //msort.merge_sort(nums,0,nums.size()-1);

        QuickSort qsort = QuickSort();
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(nums.begin(), nums.end(), g);
        qsort.quick_sort(nums,0,nums.size()-1);
        


        reverse(nums.begin(),nums.end());
        return nums;
    }
};