难度：中等
题目内容：
给定一个整数数组 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
