Python選擇排序算法僅返回最小值列表

Question

def sortList(self, list): 
    for i in range(len(list)): 
     min = list[i] 
     for j in range(i+1, len(list)): 
      if list[j] < min: 
       min = list[j] 
     list[i] = min 
    return list 

上述算法返回列表的最小值。例如，如果樣本列表是list = [4,7,9,2]，算法將返回[2,2,2,2]。

算法中的故障在哪裏？

Answer 1

那麼這裏還有一些失誤：

1. 首先，你在一個奇怪的方式計算min，因爲你每一次把它分配給list[i];和
2. 你不「交換」，你只需將最小值分配給列表的那一部分。

什麼你基本上需要的是，每次計算並i之間的最小的列表的末尾，然後或者「移動」在其他元件到右邊，或執行與該佔據元件交換的算法你想放置這個元素的地方。

我想更多後者（交換）的一點點高效，因爲它是一個O（1）操作（但注意，發現最小是爲O（n） opeation。

所以，你可以使用：

def sort_list(self,data): 
    n = len(data) # obtain the length of the list 
    for i in range(n): 
     min, minj = data[i], i # we use data[i] as the running min 
           # i as index of the smallest item 
     for j in range(i+1,n): # iterate over the remainder of the list 
      if data[j] < min: # if we find a smaller item 
       min, minj = data[j], j # update min and minj 

     # perform a swap between i and minj 
     t = data[i] 
     data[i] = min 
     data[minj] = t 
    return data 

話雖這麼說插入排序絕對是不最有效的排序算法，你最好使用內置list.sort方法或sorted函數，它們針對Python進行了優化。