k元素

Python实现查找第K⼩元素（上）--快排思想

今天抽时间实现的是查找第⼩元素算法。

问题描述：给定线性序集中个元素和⼀个整数，要求找出这个元素中第⼩的元素。

对于这个问题，⼀般可以直接想到的⽅法就是，先对这个数字进⾏排序，然后直接选取第k个元素，排序算法可以⽤我们之前实现过的归并

排序或者快速排序，这样实现的算法时间复杂度是

我们最近⼀直在学习分治思想，所以就考虑能否将分治的思想应⽤到第个元素的选择问题中，将时间复杂度降下来呢？

我们可以对数组进⾏类似快排那样将数据分成两段，得到排序后随机元的位置，如果等于，则说明就是第⼩的元素，如果⼩于

，说明第⼩的元素在随机元的左侧，否则，第⼩的元素在随机元的右侧。

对选中的⼀段重复前⾯类似快排的操作，直到找到全局第个元素。具体内容结合下⾯的代码来看：

defSelect_K(nums:list,left:int,right:int,k:int)->int:

ifleft>right:

return

ifk>len(nums)ork<=0:

return'kisoutofrange'

p=getIndex(nums,left,right)

ifk==p+1:

returnnums[p]

ifk

returnSelect_K(nums,left,p-1,k)

el:

returnSelect_K(nums,p+1,right,k)

#Select_K函数中使⽤了尾递归，可以消除栈溢出的情况，具体什么是尾递归，以后会有开⼀个专题来说

defswap(nums:list,i:int,j:int):

temp=nums[i]

nums[i]=nums[j]

nums[j]=temp

defgetIndex(nums:list,left:int,right:int)->int:

n=nums[left]

i,j=left,right

whileTrue:

whilei

i+=1

whilenums[j]>n:

j-=1

ifi>=j:

break

el:

swap(nums,i,j)

nums[left]=nums[j]

nums[j]=n

returnj

通过上⾯的⽅法，可以得到第⼩的值，但是在算法的复杂度上来看只是快排的⼀半，时间复杂度并没有降多少，但是经过⼤佬证明：当我

们使⽤随机取元(RandomGetIndex)⽅法获得随机元的时候，平均的搜索时间可以降到线性时间内，也就是平均时间复杂度为。

那么，能否找到⼀种⽅法，使得最坏情况下的搜索也能在线性时间内完成呢？答案是可以的，但是我们将在下篇博客中进⾏讲解实现。

路漫漫其修远兮，吾将上下⽽求索。

K

nk(1<=k<=n)nk

n

O(nlogn)

k

ipkp+1ikk

p+1kiki

k

k

iO(n)