一、算法
class Solution:def Partition(self, nums, low, high):pivotkey = nums[low] # 元素copied, nums[low]空了出来while low < high:while low < high and nums[high] >= pivotkey:high = high - 1 # 直到找到一个nums[high]<pivotkey位置nums[low] = nums[high] # 将其移到pivotkey的左边, High所指向的位置空了出来# 或者直到high移动到了low的位置，说明右边的值都大于pivotkey，不需要移动while low < high and nums[low] <= pivotkey:low = low + 1nums[high] = nums[low] # 最终low指针指向的位置空了出来# 完成了一趟排序，pivot key 左边的小于都小于等于它，右边的大于等于它nums[low] = pivotkeyreturn low # 此时的low代表的是Pivotkey的位置（有序分界点）# 1. 快速排序（递归分治法），每次能确定一个元素的位置，我使用的pivot key默认是最左边的值def QuickSort(self, nums, low, high):if low < high: # 递归终止条件：Low==high# print("low=", low, "high=", high)pivot_loci = self.Partition(nums, low, high)# print("pivot_loci: nums[", pivot_loci, "]=",nums[pivot_loci])# 再对左边进行sortself.QuickSort(nums, low, pivot_loci-1)# 再对右边进行sortself.QuickSort(nums, pivot_loci+1, high)def sortArray(self, nums: List[int]) -> List[int]:low = 0high = len(nums)-1self.QuickSort(nums, low, high)return nums二、例子
三、时空复杂度
1、时间复杂度
平均/最好 O(nlogn) ：每一轮确定一个元素（pivot_key）的位置（称作分区），因为总体使用的是递归分治法，不断把数组分裂成两半，所以在最理想的情况下，数组每次都对半分，递归的深度就是logn。那么每一层分区的时间 n 乘以这一层递归的深度 logn 就是总时间复杂度 nlogn.
最差 O(n^2) ：上面说了最理想的情况是数组每次对半分，递归深度等于logn，所以如果不理想的情况，比如每次选的Pivot都是最小的或者最大的，把长度为n的数组分成了 1 和 n-1，那么递归的深度就变成了n。最差的总时间复杂度就是 n^2.
2、空间复杂度
O(logn)： 递归栈的深度为logn （最好）
