0

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

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

1 回答 1

0

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

请试试这个来计算你的时间：

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
于 2013-10-08T12:51:31.373 回答