快速排序和python問題

Question

我在寫一個爲班級玩撲克的python程序，我需要對五張牌手列表進行排序。我有一個名爲wins（）的函數，它需要兩隻手，如果第一個擊中第二個，則返回True，如果不是，則返回False。我寫了一個快速排序的實現來對手的列表進行排序，並且我注意到它花費的時間遠遠超過預期，所以我將其編程爲打印每個正在排序的列表的長度。該函數如下所示：

def sort(l): 
    if len(l) <= 1: 
     return l 
    print len(l) 
    pivot = choice(l) 
    l.remove(pivot) 
    left = [] 
    right = [] 
    for i in l: 
     if wins(i, pivot) == True: 
      right.append(i) 
     else: 
      left.append(i) 
    return sort(left) + [pivot] + sort(right) 

並且當我有它排序64的手，它印： 64， 53， 39， 26， 25， 24， 23， 22， 21， 20， 19， 18， 17， 16， 15， 14， 13， 12， 11， ， 9， 8， 7， 6， 5， 4， 3， 2， 12， 7， 3， 2， 3， 2， 4， 3 ， 2， 13， 9， 6， 2， 3， 2， 2， 3， 10， 8， 2， 5， 4， 3， 2.注意中間的連續序列？我無法弄清楚它爲什麼會這樣做，但它導致快速排序，像O（n^2）那樣運行。在每次迭代中選擇最強的手作爲支點是沒有意義的，但這似乎正在發生。我忽略了什麼？評論後

Answer 1

編輯答案：

你可以試試下面的代碼和分享您的結果。它引入了一個等價類，以減少「輸或綁」（或「小於或等於」）羣體的人口，同時通過遞歸形成答案。

# modified quicksort with equivalence class. 
def sort(l): 
    if len(l) <= 1: 
     return l 
    print len(l) 
    pivot = choice(l) 
    l.remove(pivot) 
    left = [] 
    right = [] 

    # I added an equivalence class 
    pivotEquivalence = [pivot] 

    # and an equivalence partitioning 
    # to reduce number of elements 
    # in the upcoming recursive calls 
    for i in l: 
     if wins(i, pivot) == True: 
      right.append(i) 
     elif wins(pivot,i) == True: 
      left.append(i) 
     else 
      pivotEquivalence.append(i) 
    return sort(left) + pivotEquivalence + sort(right) 

======

而是隨機選擇的支點，儘量取中間的索引元素。平均而言，它將保證O（N log N）。

同樣對於O符號，您需要進行許多模擬來收集經驗數據。只有一個例子可能會造成誤導。

試着打印數據透視表，它也是索引。通過random.shuffle（列表）隨機清單，然後再次嘗試查看分配。只要確保系統時間播種。

您可以發送完整的代碼和您的數據爲社區重複該問題嗎？

此致 Umut