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]

快速排序是先将一个元素排好序，然后再将剩下的元素排好序。

思路：快速排序的正确理解方式及运用 

先对数组nums进行随机洗牌，得到无序数组；然后开始快排（先序遍历、自顶向下），

用 partition 函数把 nums[p] 这个元素排到正确的位置（左边都比它小，右边都比它大——二叉搜

索树），然后对[low,p-1]、[p+1,high]这两个子数组进行递归，用 partition 函数把剩下的元素也

排好序。

随机洗牌：洗牌算法详解：你会排序，但你会打乱吗？

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        shuffle(nums);//随机洗牌
        sort(nums,0,nums.size()-1);
        return nums;
    }
    void shuffle(vector<int>& nums)
    {
        srand(time(NULL));
        int n=nums.size();
        for(int i=0;i//产生n！种可能
        {
          int index=i+rand()%(n-i);//随机生成[i,n-1]范围内的一个数作为数组下标
          swap(nums,i,index);
        }
    }
    void swap(vector<int>& nums,int i,int index)
    {
        int tmp=0;
        tmp=nums[i];
        nums[i]=nums[index];
        nums[index]=tmp;
    }
    void sort(vector<int>& nums,int low,int high)
    {
        if(low>=high)
        return ;
        //对nums[low..high]进行切分，使得nums[low..p-1]<=nums[p]
        int p=partition(nums,low,high);
        sort(nums,low,p-1);
        sort(nums,p+1,high);
    }
    int partition(vector<int>& nums,int low,int high)
    {
        int pivot=nums[low];//以第一个元素作为枢轴
        int i=low+1,j=high;
        while(i<=j)
        {
            while(i//此while结束时恰好nums[i]>pivot
            {
                i++;
            }
            while(j>low&&nums[j]>pivot)//此while结束时恰好nums[j]<=pivot
            {
                j--;
            }
            if(i>=j)//如果i>=j，跳出循环，j的位置就是pivot应该被放到的正确位置 
            {
                break;
            }
            swap(nums,i,j);//交换不符合枢轴左边小、右边大规则的两个元素
        }
        swap(nums,low,j); //将pivot放到合适的位置，即pivot左边元素小，右边元素大
        return j;//返回pivot的位置
    }
};