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进行了优化。