为什么这个python代码需要这么久？

Question

好吧，我有这比较合并排序和选择排序的Python代码，但它是永远。当从n = 0到90,000（列表大小）完成时，对列表排序只需要约3秒。按照这个逻辑，它将需要大约10 * 3 * 9秒（贯穿次数*持续时间*递增遍历[我们以10,000开始，然后是20,000，然后是30,000等））。然而，这需要更长的时间。

import time 
import random 

# Selection Sort Code # 
def maxIndex(J): 
    return J.index(max(J)) 

def swap(LCopy, i, j): 
    temp = LCopy[i] 
    LCopy[i] = LCopy[j] 
    LCopy[j] = temp 

# Implementation of selection sort 
def selectionSort(L): 
    for i in range(len(L)-1, 1, -1): 
     j = maxIndex(L[0:i+1]) 
     swap(L, i, j) 

# Merge Sort Code # 
# Assumes that L[first:mid+1] is sorted and also 
# that L[mid: last+1] is sorted. Returns L with L[first: last+1] sorted 

def merge(L, first, mid, last): 

    i = first # index into the first half 
    j = mid + 1 # index into the second half 

    tempList = [] 

    # This loops goes on as long as BOTH i and j stay within their 
    # respective sorted blocks 
    while (i <= mid) and (j <= last): 
     if L[i] <= L[j]: 
      tempList.append(L[i]) 
      #print L[i], "from the first block" 
      i += 1 
     else: 
      tempList.append(L[j]) 
      #print L[j], "from the second block" 
      j += 1 

    # If i goes beyond the first block, there may be some elements 
    # in the second block that need to be copied into tempList. 
    # Similarly, if j goes beyond the second block, there may be some 
    # elements in the first block that need to be copied into tempList 
    if i == mid + 1: 
     tempList.extend(L[j:last+1]) 
     #print L[j:last+1], "some elements in second block are left over" 
    elif j == last+1: 
     tempList.extend(L[i:mid+1]) 
     #print L[i:mid+1], "some elements from first block are left over" 

    L[first:last+1] = tempList 
    #print tempList 


# The merge sort function; sorts the sublist L[first:last+1]  
def generalMergeSort(L, first, last): 
    # Base case: if first == last then it is already sorted 

    # Recursive case: L[first:last+1] has size 2 or more 
    if first < last: 
     # divide step 
     mid = (first + last)/2 

     # conquer step 
     generalMergeSort(L, first, mid) 
     generalMergeSort(L, mid+1, last) 

     # combine step 
     merge(L, first, mid, last) 

# Wrapper function 
def mergeSort(L): 
    generalMergeSort(L, 0, len(L)-1) 



m = 10 
n = 100000 
n_increments = 9 
baseList = [ random.randint(0,100) for r in range(n) ] 


i = 0 

while i < n_increments: 
    j = 0 
    sel_time = 0 
    mer_time = 0 

    while j < m: 
     # Do a Selection Sort # 
     x = time.clock() 

     selectionSort(baseList) 

     y = time.clock() 

     sel_time += (y - x) 

     random.shuffle(baseList) 

     # Do a Merge Sort # 

     x = time.clock() 

     mergeSort(baseList) 

     y = time.clock() 

     mer_time += (y - x) 

     random.shuffle(baseList) 

     j += 1 
    print "average select sort time for a list of", n, "size:", sel_time/m 
    print "average merge sort time for a list of", n, "size:", mer_time/m 

    j = 0 
    i += 1 
    n += 10000 

Answer 1

因为您正在使用O（n^2）排序算法。这意味着如果您加倍n，算法运行时间会延长4倍。请注意，你开始在100,000而不是10,000