快速氣泡排序

-5

def bubble(lst): 
    swap = 'True' 
    counter = 0 
    n = len(lst) 
    m = len(lst) 
    while swap == 'True': 
      for j in range(n-1): 
        if lst[j] > lst[j+1]: 
          lst[j],lst[j+1] = lst[j+1],lst[j] 
          counter += 1 
          swap = 'True' 
        else: 
          swap = 'False' 
      n = n - 1 
    return counter

如何縮短此功能所需的時間，因爲我想在更大的列表上使用它。快速氣泡排序

來源

2011-11-02 user986956

你在殺我...... –

從我的角度來看，沒有什麼叫做「快速冒泡排序」，泡泡排序的定義很慢，它是O（n * n）!!!! –

http://www.sorting-algorithms.com/ –

更改算法。

使用MergeSort或QuickSort。

BubbleSort是O（n * n）。它存在的唯一原因是向學生展示他們應該如何排序陣列:)

MergeSort是最壞的情況O（n log n）。快速排序是O（n * n）最差情況，平均情況O（n日誌n），但是具有「低常量」，所以它通常比合並排序更快。

在網上搜索他們。

，如果我沒有錯......（不要在我憤怒，如果我請）......我想我明白你想要做什麼：

def bubble(lst): 
    n = len(lst) 
    while True 
     newn = 0 
     for i in range(1, n-1): 
      if lst[i-1] > lst[i]: 
       lst[i-1],lst[i] = lst[i],lst[i-1] 
       newn = i 
       counter += 1 
     if newn <= 0: 
      return counter 
     n = newn

的複雜性卻會總是O（n * n），所以你不會注意到任何重要的區別。

例如：

如果你的列表是2000項，並使用冒泡排序，O（2000 * 2000）= 4000000個循環步驟。這是巨大的。

O（2000 * log2 2000）=循環步驟的大約21931，這是可管理的。

來源

2011-11-02 05:05:36

-2

def bubble(lol): 
    lol.sort() 
    return lol

來源

2011-11-02 08:34:11 Noxville

除了你的變量名稱，這實際上是一個答案。但是，應該指出，這種排序方式就地排序，並且不會返回排序後的副本，就像它似乎表明的那樣。 – balpha

@balpha - 如果他只是返回'lol.sort（）'，它會工作。「＃： – thegrinner

Comments：arg應該是'lol'而不是'list';使用'list'「陰影」一個內置的關鍵字'list';是的，這會改變'lol'，所以在Python最佳實踐中它應該返回'None'。而@thegrinner，沒有不行的; 'list.sort（）'返回'None'，因爲我上面提到的最佳做法叫做「Command-Query Separation」。 http://en.wikipedia.org/wiki/Command-query_separation – steveha

快速氣泡排序

回答

相關問題