如果枢轴不是中期，快速选择会采取不同的行动

Question

好吧，所以我开发了一个通用的快速选择函数，它用于查找列表的中位数。

k = len(aList)//2 and the list is aList = [1,2,3,4,5]

那么，如果每次从列表的第一项开始透视，程序的行为将如何不同。我必须在中心吗？另外，我应该从哪里开始time.clock((以查找函数的经过时间。这是代码

def quickSelect(aList, k)
   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)
   if k >= m and k<m + count:
      return pivot
   elif m > k:
      return quickSelect(smallerList,k)
   else:
      return quickSelect(largerList, k - m - count)

Answer 1

我认为将

枢轴放在开头没有任何问题。但这只是初始化枢轴。枢轴的整个想法通常是找到中间元素。

请尝试以下方法进行时间计算：

import time
start_time = 0
aList = [1,2,3,4,5]
k = len(aList)//2  
def quickSelect(aList, k):
    start_time = time.time()
#     print "%10.6f"%start_time
#     pivot = aList[0]
    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)
        if k >= m and k < m + count:
            print "Pivot", pivot
#             print "%10.6f"%time.time()
            print "time: ", time.time() -start_time
            return pivot
        elif m > k:
            return quickSelect(smallerList, k)
        else:
            return quickSelect(largerList, k - m - count)

quickSelect(aList, k)

在这种情况下，您的列表的时间为零非常小。如果我误解了你的问题，请告诉我。

输出：

Pivot 3
time:  0.0