冒泡排序錯誤

Question

我正在嘗試編寫和優化冒泡排序，但我的代碼實際上並沒有通過列表排序。關於爲什麼它提前停止的任何建議？

#!/usr/bin/env python 

from random import * 
import time 

def bubble(lst): 
    counter = 0 
    n = len(lst) 
    while n > 0: 
     temp = 0 
     for i in range(1, n - 1): 
      if lst[i] > lst[i + 1]: 
       lst[i], lst[i + 1] = lst[i + 1], lst[i] # swap 
       temp = i 
       counter += 1 # to compare the speed to the 
          # unoptimized bubble sort 
      n = temp 
    return counter 

def main(): 
    lst = range(10) 
    shuffle(lst) 
    print lst 
    start = time.time() 
    counter = bubble(lst) 
    print lst 
    end = time.time() 
    print counter 
    print "time", end - start 

main() 

Answer 1

這應該修復它：

def bubble(lst): 
    counter = 0 
    n = len(lst) 
    while n > 0: 
      temp = 0 
      for i in range(0,n-1): # <- first element is at position 0 
        if lst[i] > lst[i+1]: 
          lst[i],lst[i+1] = lst[i+1],lst[i] #swap 
          temp = i+1 # <- the last swapped position 
          counter += 1 
      n = temp 
    return counter