Python中的quickSelect硬件

Question

我已经得到了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)

Answer 1

首先，您让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将/不/包括pivot，因此count (发生pivot的次数)将是主列表的长度减去较小和较大列表的组合长度。

现在，如果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)

这个函数会一遍又一遍地运行(比线性排序快得多)，一旦满足，就会给你轴的返回。在这种情况下，Pivot将是中间值。

希望这能有所帮助！