快速排序（TOP-K问题汇总）
今天刷题刷到了排序类的问题，之前大多都选择了sort()或sorted()解决，并且调包的速度基本比自己手写快排快几十倍。但是快速排序的思想是非常重要的，因此记录一下快速排序及其相关TOP-K类问题通用解法。
需要注意的是，快速排序不适合解决存在重复元素的排序问题。
首先写partition函数，partition函数的作用是随机找一个元素（以第一个元素为例），在列表中找到它的合适位置（最终返回它在列表中的正确index），即最后其左边的元素均比它小，右边的元素均比它大。
def partition(nums, left, right):pivot = nums[left]#初始化一个待比较数据i,j = left, rightwhile(i < j):while(i<j and nums[j]>=pivot): #从后往前查找，直到找到一个比pivot更小的数j-=1nums[i] = nums[j] #将更小的数放入左边while(i<j and nums[i]<=pivot): #从前往后找，直到找到一个比pivot更大的数i+=1nums[j] = nums[i] #将更大的数放入右边#循环结束，i与j相等nums[i] = pivot #待比较数据放入最终位置return i #返回待比较数据最终位置
快速排序写法
# 快速排序def quicksort(nums,left,right):if left < right:index = partition(nums,left,right)quicksort(nums,left,index-1)quicksort(nums,index+1,right)
接下来是一系列的TOP-K问题解法：
首先写一个TOP-K切片函数：
将快速排序改成快速选择，即我们希望寻找到一个位置，这个位置左边是k个比这个位置上的数更小的数，右边是n-k个比该位置上的数大的数，将它命名为topk_split，找到这个位置后停止迭代，完成了一次划分。（因此，这个位置左边和右边的元素顺序并未排序，只是总体来说左边小于它，右边大于它）
def topk_split(nums,left,right,k):index = partition(nums,left,right)if index == k:returnelif index < k:topk_split(nums,index+1,right,k)else:topk_split(nums,left,index-1,k)
接下来就依据上面的partition和topk_split函数解决一切TOP-K问题！
获得前K小的元素
def topk_min(nums,k):topk_split(nums,0,len(nums)-1,k)return nums[:k]
获得前K大的元素
def topk_max(nums,k):# partiton是按从小到大的顺序划分，因此把左边划分为前n-K个小的数，# 右边就是前K大的数topk_split(nums,0,len(nums)-1,len(nums)-k)return nums[len(nums)-k:]
获取第K小的元素
def topk_small(nums,k):topk_split(nums,0,len(nums)-1,k)return nums[k-1]
获取第K大的元素
def topk_big(nums,k):topk_split(nums,0,len(nums),len(nums)-k)return nums[len(nums)-k]