难度：中等

题目内容：

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

示例 1：

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

输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

题解：

题目内容很简单，不过直接用库函数就没什么意思了，这次用快速排序
快速排序是一种递归的思想，能实现O(nlogn)的时间复杂度
看到这个肯定会想是要进行二分了
那么我们递归的模式就应该是把序列划分成前后两部分，并使得前一部分数据都比后一部分数据小。
这样当递归完成后，数据就是有序升序排列了。
那么首先我们先有一个需要被递归调用的函数quickSort(self,nums,l,r)对nums数组内[l,r]部分进行排序，然后在递归调用它对(l,k),(k+1,r)进行排序
那么问题的关键就是在这个quickSort里面我们要做什么了。
我们应当把序列划分成一个能从一个位置断开，然后前面的数都比后面的数小的序列。

最后的数为主元

第一种方法是把最后一个数当作划分节点。
然后选取第一个下标i来从前向后进行扫描，扫描到第一个比主元大的数，停下。
选取第二个下标j来从后向前扫描，扫描到第一个比主元小的数，停下。
比较一下i和j的大小，如果i仍然小于j
就交换这两个数的位置
然后重复上面的过程，只不过不要从开头结尾扫描，可以省略掉已经扫描的内容了，直到i<j，此时我们可以明显的发现，第一个比主元小的数在i(也就是j+1)，第一个比主元大的数在j(就是i-1)，那么i和j就可以作为我们的分界坐标了。
函数实现为

    def Partition(self,nums,l,r):## 选取最后一个主元
        p = nums[r]
        i = l
        j = r-1
        while True:
            while nums[i]< nums[r] and i <= r:
                i += 1
            while nums[j]> nums[r] and j >= l:
                j -= 1
            #交换二者位置
            if i<j:
                nums[i],nums[j] = nums[j],nums[i]
                i += 1
                j -= 1
            else:
                break
        return j

随机主元

除此之外，由于我们不知道选取哪个数当这个划分节点，我们也不妨直接随机抽取一位幸运观众。
可以有函数实现为

    def Partition(self,nums,l,r):## 随机选取主元
        p = random.randint(l, r)#随机选取主元
        nums[p], nums[r] = nums[r], nums[p]#和末尾交换位置
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:#每当有小于末尾（换过去的主元）时，交换位置
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

实现

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quickSort(nums,0,len(nums)-1)
        return nums
    def quickSort(self,nums,l,r):#从l到r的排序
        if r - l <= 0:
            return
        m = self.Partition(nums, l, r)
        self.quickSort(nums, l, m - 1)
        self.quickSort(nums, m + 1, r)
    def Partition(self,nums,l,r):## 随机选取主元
        p = random.randint(l, r)#随机选取主元
        nums[p], nums[r] = nums[r], nums[p]#和末尾交换位置
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:#每当有小于末尾（换过去的主元）时，交换位置
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i