Python中的选择排序不起作用

Question

我正在学习算法，从冒泡排序开始，现在开始学习选择排序。下面是我正在使用的代码：

test = [5, 3, 6, 1, 8, 7, 2, 4]

def selection_sort(items):
    for i in range(0, len(items)-1):
        minIndex = i
        for j in range(i + 1, len(items)):
            if items[j] < items[minIndex]:
                minIndex = j
            if minIndex != i:
                items[i], items[minIndex] = items[minIndex], items[i]

print("Before: ", test)
selection_sort(test)
print("After: ", test)

问题是我从这里得到的输出是：[1, 3, 4, 2, 5, 6, 7, 8]当我再次运行它时，我得到了正确的输出：[1, 2, 3, 4, 5, 6, 7, 8]

你知道为什么它被追上了吗？谢谢!

Answer 1

您实际上这样做是错误的，在每次迭代中，您都会用minIndex替换ith position元素，即使它不是实际的minIndex (您是在内部循环中进行的)。

您需要在内部循环之外进行交换，以便在内部循环中找到具有最小值元素的索引，然后交换ith和minIndex位置元素。

示例：

>>> test = [5, 3, 6, 1, 8, 7, 2, 4]
>>> def selection_sort(items):
...     for i in range(0, len(items)-1):
...         minIndex = i
...         for j in range(i + 1, len(items)):
...             if items[j] < items[minIndex]:
...                 minIndex = j
...         if minIndex != i:
...             items[i], items[minIndex] = items[minIndex], items[i]
...
>>> selection_sort(test)
>>> test
[1, 2, 3, 4, 5, 6, 7, 8]