python - 为什么我的随机主元快速排序比固定主元快速排序慢？

Question

使用随机基准快速排序:

def quicksort(arr): # with random index
    if (len(arr) <= 1):
        return arr
    else:
        grt_arr = []
        less_arr = []
        rand_indx = random.randint(0,len(arr)-1)    
        pivot = arr[rand_indx] # picking up a random index
        #for ele in arr[1:]:
        for ele in (arr[0:rand_indx]+arr[rand_indx+1:]):
            if (ele <= pivot):
                less_arr.append(ele)
            elif (ele > pivot):
                grt_arr.append(ele)

    return quicksort(less_arr)+[pivot]+quicksort(grt_arr)

固定主元的快速排序:

def quicksortfixedpivot(arr): # with fixed index
    if (len(arr) <= 1):
        return arr
    else:
        grt_arr = []
        less_arr = []
        pivot = arr[0] # picking up a fixed 0 index
        for ele in arr[1:]:
            if (ele <= pivot):
                less_arr.append(ele)
            elif (ele > pivot):
                grt_arr.append(ele)

    return quicksortfixedpivot(less_arr)+[pivot]+quicksortfixedpivot(grt_arr)

在以下列表上运行算法后，我得到以下结果。

# create a list of random numbers
arr1 = (random.sample(range(0,10000000),1000000))

运行时间如下所示:

%%time
out1 = (quicksort(arr1))

CPU times: user 8.74 s, sys: 219 ms, total: 8.95 s Wall time: 9.22 s

%%time
out2 = (quicksortfixedpivot(arr1))

CPU times: user 6.39 s, sys: 138 ms, total: 6.53 s Wall time: 6.54 s

为什么我的 quicksortfixedpivot 比使用固定主元的快速排序更快？

Answer 1

问题是，在您的随机索引中，代码 rand_indx = random.randint(0,len(arr)-1) 发生了超过 600,000 次。虽然每次通话花费的时间很少，但加起来会很累。

自己尝试一下:只需将对 random.randint(0,len(arr)-1) 的调用添加到您的固定基准并再次计时。