我得到了以下用于 quickSelect 算法的伪代码。我对一些事情有点困惑，当我调用 quickSelect 方法时，我为“k”发送了什么。另外，因为我需要在方法的开头声明 count = 0，所以在 quickSelect 的递归调用中它总是会设置回 0，这不是我需要发生的事情谢谢你的帮助，我已经包含了伪-代码以及下面我的代码；
Function quickSelect(aList, k):
If aList is not empty:
pivot <- Choose the element at position (len(alist)//2)
smallerList <- All elements of aList smaller than pivot
largerList <- All elements of aList larger than pivot
count <- the number of occurences of pivot value in aList
m <- the size of smallerList
if k >= m and k < m + count then:
return pivot
if m > k:
return quickSelect(smallerList,k)
else:
return quickSelect(largerlist, k-m-count)
这是我想出的:
def quickSelect(aList, k):
pivot = aList[len(aList)//2]
smallerList = aList[:pivot]
largerList = aList[pivot:]
m = len(smallerList)
count = 0
for i in aList:
if i == pivot:
count = count + 1
if k >= m and k < m + count:
return pivot
if m > k:
return quickSelect(smallerList, k)
else:
return quickSelect(largerList, k-m-count)
请您参考如下方法:
首先，您有 smallerList 和 largerList 根据它们的索引而不是它们的值从枢轴的任一侧获取内容。 Pivot 应该将数字除以索引的内容，而不是索引的位置(比如如果索引为 5，则所有小于数字 5 的条目都需要分配给 smallerList，并且所有更大的数字需要分配给大于 5 的 largerList。
这可以通过一个简单的 for 循环来完成:
if len(aList)!=0:
pivot=aList[(len(aList)//2)]
smallerList = []
for i in aList:
if i<pivot:
smallerList.append(i)
largerList=[]
for i in aList:
if i>pivot:
largerList.append(i)
m=len(smallerList)
count=len(aList)-len(smallerList)-len(largerList)
smallerList 和 largerList 将/不/包含主元，因此计数(主元发生的次数)将是主列表的长度减去主列表的组合长度较小和较大的列表。
现在如果k(第k小的数)大于等于m，小列表的长度，且k小于小列表的长度+pivot的个数，需要返回pivot，因为它是您要查找的第 k 个最小的数字。
if k >= m and k<m + count:
return pivot
或者，如果较小列表的长度大于 k，则仅使用 smallerList 而不是完整列表再次运行快速选择。
elif m > k:
return quickSelect(smallerList,k)
否则，使用较大列表而不是完整列表再次运行快速选择，并查找 k - 较小列表的长度 - 枢轴计数
else:
return quickSelect(largerList, k - m - count)
此函数将一遍又一遍地自行运行(比线性排序快得多)，一旦满足就会返回基准。在这种情况下，枢轴将是中位数。
希望这对您有所帮助!
