兩種排序功能之間的效率

我已經創建了兩個函數，它們將整數從最低值到最高值再從低到低排序。這種排序是否存在？無論如何，我有以下兩個我創建的產生相同輸出的排序函數。我想知道哪個是最有效的兩個？我可以對此做出任何改進嗎？兩種排序功能之間的效率

sortMiddleMax1
- 創建一個新的反向由2
sortMiddleMax2
- 排序的排序原始
- 開始的列表從索引1至列表步驟的長度列表就地
- 開始從最後一個索引爲0的步驟由2

我試圖使所述第二比第一更有效。我沒有在內存中創建一個新列表，而是追加到最後，而不是將整個列表推向正確的位置。我在這個假設中糾正了嗎？

功能

def sortMiddleMax1(aList=None, verbose=False): 
    if aList == None or len(aList) < 2: 
    return aList 
    else: 
    sList = sorted(x, key=None, reverse=True) 
    if verbose: print sList 
    index = 1 
    while index < len(sList): 
     tmp = sList[index] 
     del sList[index] 
     sList.insert(0, tmp) 
     index+=2 
     if verbose: print sList 
    return sList 

def sortMiddleMax2(aList=None, verbose=False): 
    if aList == None or len(aList) < 2: 
    return aList 
    else: 
    aList.sort() 
    if verbose: print aList 
    index = len(aList)-1 
    while index > 0: 
     tmp = aList[index] 
     del aList[index] 
     aList.append(tmp) 
     index-=2 
     if verbose: print aList 
    return aList

主要

x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8] 
print '############# sortMiddleMax1 #############' 
x1 = sortMiddleMax1(x, True) 
print '############# sortMiddleMax2 #############' 
x2 = sortMiddleMax2(x, True)

輸出

############# sortMiddleMax1 ############# 
[9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1] 
[8, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1] 
[8, 8, 9, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1] 
[6, 8, 8, 9, 8, 7, 5, 5, 4, 3, 3, 2, 1, 1] 
[5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 3, 2, 1, 1] 
[3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 2, 1, 1] 
[2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1, 1] 
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1] 
############# sortMiddleMax2 ############# 
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9] 
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9] 
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 8] 
[1, 1, 2, 3, 3, 4, 5, 5, 6, 8, 8, 9, 8, 7] 
[1, 1, 2, 3, 3, 4, 5, 6, 8, 8, 9, 8, 7, 5] 
[1, 1, 2, 3, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4] 
[1, 1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3] 
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

來源

2013-02-28 Mr. Polywhirl

您是否嘗試對他們每個人進行計時以查看哪個是最快的？ – 2013-02-28 02:33:20

我不確定您的定義是否定義良好。'[1,2,3,4,5,10,9,8,7,6]'會是一個有效的結果嗎？它上升，然後下降！如果無效，則需要準確指定輸出的前半部分和後半部分是如何相關的。 – Blckknght 2013-02-28 02:36:45

@大衛我沒有計時。我不是在尋找速度，而是尋找內存佔用。 – 2013-02-28 02:52:22

您可以使用Python的擴展切片。 [::2]意味着採取每第二個元素。 [::-2]意味着從末端開始每隔一個元素並向後工作。這裏第一個片段從0開始爲偶數長度列表，1爲奇數長度列表

>>> x = [1, 4, 6, 8, 3, 5, 7, 1, 5, 8, 3, 9, 2, 8] 
>>> x = sorted(x) 
>>> x[len(x)%2::2] + x[::-2] 
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

來源

2013-02-28 02:54:24

太棒了！每2片很好。從來沒有嘗試過，因爲我是一個有抱負的蟒蛇。 – 2013-02-28 03:08:14

您可以使用列表切片得到的結果無線對於循環：

x = sorted([1,4,6,8,3,5,7,1,5,8,3,9,2,8]) 
x2 = x[::2] + x[1::2][::-1]

來源

2013-02-28 02:48:39 HYRY

我懷疑你的兩個當前版本執行完全相同。但是，它們都可以通過使用切片來獲得列表中的值而不是通過刪除和插入值來改進。

每個del每個insert爲O(N)和你正在做的每一個N/2，這樣的排序將是O(N^2)。切片也是O(N)，但只需要做兩次。漸近式O(N log N)所花費的時間將佔主導地位。

def sortMiddle3(aList): 
    s = sorted(aList) # sort the provided list 

    # now take the even indexed items, followed by the odd indexes in reverse 
    if len(s) % 2 == 0: # is the number of items even? 
     return s[::2] + s[-1::-2] # if so, the last item has an odd index 
    else: 
     return s[::2] + s[-2::-2]

輸出示例：

>>> x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8] 
>>> sortMiddle3(x) 
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

來源

2013-02-28 02:48:49 Blckknght

'sorted（）'已經返回列表 – 2013-02-28 02:56:01

哦，你是對的。我一直在忘記它是Python 3中仍然存在的少數功能之一（而不是生成器）。我會更新我的代碼。 – Blckknght 2013-02-28 02:58:55

很好的解釋。我忘記檢查我的原始長度甚至奇數，但它仍然成功。 – 2013-02-28 03:09:39

兩種排序功能之間的效率

回答

相關問題