/*
 * @lc app=leetcode.cn id=912 lang=cpp
 *
 * [912] 排序数组
 */

// @lc code=start

// 归并排序
// class Solution {
// private:
//     vector<int> temp;

//     void merge(vector<int>& nums, int lo, int mid, int hi) {
//         for (int i = lo; i <= hi; i++) {
//             temp[i] = nums[i];
//         }
//         int i = lo, j = mid + 1;
//         for (int p = lo; p <= hi; p++) {
//             if (i == mid + 1) {
//                 nums[p] = temp[j++];
//             } else if (j == hi + 1) {
//                 nums[p] = temp[i++];
//             } else if (temp[i] > temp[j]) {
//                 nums[p] = temp[j++];
//             } else {
//                 nums[p] = temp[i++];
//             }
//         }
//     }

//     void sort(vector<int>& nums, int lo, int hi) {
//         if (lo == hi) return;
//         int mid = lo + (hi - lo) / 2;
//         sort(nums, lo, mid);
//         sort(nums, mid + 1, hi);
//         merge(nums, lo, mid, hi);
//     }
// public:
//     vector<int> sortArray(vector<int>& nums) {
//         temp.resize(nums.size(), 0);
//         sort(nums, 0, nums.size() - 1);
//         return nums;
//     }
// };



//快速排序
class Solution {
private:
    int partition(vector<int>& nums, int lo, int hi) {
        int pivot = nums[hi];
        int i = lo - 1;
        for(int j = lo; j <= hi - 1; ++j) {
            if (nums[j] <= pivot) {
                i += 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i+1], nums[hi]);
        return i+1;
    }

    int randomized_partition(vector<int>& nums, int lo, int hi) {
        int i = rand() % (hi - lo + 1) + lo; //随机选取主元
        swap(nums[i], nums[hi]);
        return partition(nums, lo, hi);
    }

    void randomized_quicksort(vector<int>& nums, int lo, int hi) {
        if (lo < hi) {
            int pos = randomized_partition(nums, lo, hi);
            randomized_quicksort(nums, lo, pos - 1);
            randomized_quicksort(nums, pos + 1, hi);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size()-1);
        return nums;
    }
};
// @lc code=end