题解 | #寻找第K大#

def findKth(self, a, n, K):
#第K大，即第n-K小，因此我们可以将最终排序位置为n-K的值作为目标位置；
if a==None or K>n:return None
low,high=0,n-1
#1.首先找到第一个最终位置上的元素所在的位置pos
pos=Partition(a, low, high)
#2.如果该位置pos是目标位置，那么直接返回pos位置上的数即可，否则二分快排；
while pos!=n-K:
#3.如果当前pos位置比目标位置大，则目标位置一定在pos左侧,否则在右侧
if pos>n-K:
#3.1对pos左侧部分进行快速排序
high=pos-1
#3.2在左侧部分找到一个最终位置元素所在位置pos
pos=Partition(a, low, high)
else:
#3.3对pos右侧部分进行快速排序
low=pos+1
#3.2在右侧部分找到一个最终位置元素所在位置pos
pos=Partition(a, low, high)
#4.返回目标位置的值
return a[pos]

def Partition(arr,low,high):
temp=arr[low]
while low<high:
while low<high and arr[high]>=temp:
high-=1
arr[low]=arr[high]
while low<high and arr[low]<=temp:
low+=1
arr[high]=arr[low]
arr[low]=temp;
return low