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

问题描述 投票:0回答:2

我正在尝试实现选择排序,但它没有像算法中所说的那样平移,我对赋值运算符做错了吗?

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]))`
python list
2个回答
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])

新的代码块找到超过i的最小值的索引,该索引存储在min_i中。


0
投票

我发现问题是由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]

© www.soinside.com 2019 - 2024. All rights reserved.