1

我得到了以下 quickSelect 算法的伪代码。我对一些事情有点困惑，当我调用 quickSelect 方法时，我要为“k”发送什么。另外，因为我需要在方法的开头声明 count = 0，所以它总是会在 quickSelect 的递归调用中设置回 0 这不是我需要发生的谢谢你的帮助，我已经包含了 Pseudo -code 以及我下面的代码；

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)
4

1 回答 1

6

首先，您拥有smallerList并largerList根据它们的索引而不是它们的值从枢轴两侧获取内容。Pivot 应该将数字除以索引的内容，而不是索引的位置（例如，如果 index 为 5，则所有小于数字 5 的条目都需要分配给smallerList，并且所有更大的数字都需要分配largerList给大于 5。

这可以通过一个简单的 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 小于较小列表的长度 + 枢轴的计数，则需要返回枢轴，因为它是您正在寻找的第 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)

这个函数会一遍又一遍地运行（比线性排序快得多），一旦满足就会给你返回枢轴。在这种情况下，枢轴将是中位数。

希望这可以帮助！

于 2012-10-17T15:33:09.290 回答