如何修复此选择排序逻辑错误？

Question

我正在尝试实现选择排序，但它并不像算法中所说的那样，我是不是用赋值操作符做错了什么？

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]))`

Answer 1

这个问题是因为当您调用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])

新的代码块查找存储在min_i中的i之后的最小值的索引。

Answer 2

我发现问题是由list_1.index( val )引起的，因为每次它都会在列表的开头搜索val，为了解决这个问题，使用第二个参数就足够了(val，list_1.index)

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