Python 中的选择排序工作到位

Question

我已经编写了这个“就地”工作的选择排序算法。我想对以下列表进行排序：[8,3,1,7,4,10,5,9,2,6]。当我运行算法时，我得到以下输出： [10、2、3、4、5、6、7、8、9、10]。

def selectionSortInPlace(listToSort):
    index = 0
    for i in range(0, len(listToSort)):
        value = listToSort[i]
        index = 0
        for j in range(i+1, len(listToSort)):
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp
    
unsortedList = [8,3,1,7,4,10,5,9,2,6]
selectionSortInPlace(unsortedList)
print(unsortedList)

Answer 1

您的错误是您设置了 index = 0 和 value = listToSort[i]，并且即使 for 循环没有更新这些值也继续进行交换。

解决此问题的一种方法是将这些值设置为 None，然后如果它们没有实际值则继续循环：

def selectionSortInPlace(listToSort):
    for i in range(0, len(listToSort)):
        value = None
        index = None
        for j in range(i+1, len(listToSort)):
            print(j)
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        if index is None:
            continue
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp

另一种选择是设置 index = i 使其与 value 保持同步，即使 for 循环也从不更新（这只是使交换成为 no-op 在那种情况下):

def selectionSortInPlace(listToSort):
    for i in range(0, len(listToSort)):
        index = i
        value = listToSort[i]
        for j in range(i+1, len(listToSort)):
            print(j)
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp

您可以通过使用 enumerate（它可以让您自动迭代索引和值，而不是必须按索引迭代然后查找值）和元组来稍微简化代码赋值（它允许你在没有 temp 变量的情况下进行交换）：

def selectionSortInPlace(listToSort):
    for i, a in enumerate(listToSort):
        k = i
        for j, b in enumerate(listToSort[i+1:], i+1):
            if b < a:
                k, a = j, b
        listToSort[i], listToSort[k] = listToSort[k], listToSort[i]

您可以使用 min 函数使其更简单，因为它会自动进行内部迭代以找到适合您的最小值：

def selectionSortInPlace(listToSort):
    for i, _ in enumerate(listToSort):
        j, _ = min(enumerate(listToSort[i:], i), key=lambda j_: j_[1])
        listToSort[i], listToSort[j] = listToSort[j], listToSort[i]

Python 中的选择排序工作到位

Selection Sort in Python working in place

python

sorting

algorithm

selection-sort