我正在尝试实现选择排序,但它没有像算法中所说的那样平移,我对赋值运算符做错了吗?
def selection_sort(list_1):
for i in range(len(list_1)):
val = min(list_1[i:])
list_1[i],list_1[list_1.index(val)] =list_1[list_1.index(val)], list_1[i]
print (list_1)
print(selection_sort([3,3,4,3,465,45,346,5,456,545,345345,345]))`
问题是因为当你调用index
函数时,数组中有多个具有相同值的数字。因此,它选择它在整个数组中看到的第一个匹配数字,这可能是已经排序的值(在当前的i
之前)。
这是一种更好的方法:
def selection_sort(list_1):
for i in range(len(list_1)):
min_val = list_1[i]
min_i = i
for j in range(i + 1, len(list_1)):
if list_1[j] < min_val:
min_val = list_1[j]
min_i = j
list_1[i], list_1[min_i] = list_1[min_i], list_1[i]
print (list_1)
selection_sort([3,3,4,3,465,45,346,5,456,545,345345,345])
新的代码块找到超过i
的最小值的索引,该索引存储在min_i
中。
我发现问题是由list_1.index(val)引起的,因为每次它会在列表的开头搜索val,为了解决这个问题就足以使用像list_1.index这样的第二个参数(val,start)
def selection_sort(list_1):
for i in range(len(list_1)):
val = min(list_1[i:])
temp = list_1[i]
list_1[list_1.index(val, i)], list_1[i] = temp, val
print (list_1)
selection_sort([3,3,4,3,465,45,346,5,456,346,456,545,345345,345])
结果是[3,3,3,4,5,45,345,346,346,456,456,465,545,345345]