选择排序实现不考虑更新列表

Question

我正在尝试在Python中实现选择排序算法。我的第一个for循环不考虑更新列表。如何克服这个问题？

def SelectionSort(a):
    for m_index,x in enumerate(a[:-1]):
        pos = m_index
        temp = x
        for index,y in enumerate(a[pos+1:]):
            if y < temp :
                temp = y
                to_swap = len(a) - len(a[pos+1:]) + index
            else:
                continue
        #swapping positions
        temp_var = a[to_swap]
        a[to_swap] = a[pos]
        a[pos] = temp_var
    return a

print(SelectionSort(a))

Answer 1

您有两个错误：

1. x的值将从原始数组的副本中获取。同时可能发生的交换是在原始数组上，而x只会从使用a[:-1]制作的副本中获取下一个值。解决此问题的一种方法是忽略x，而只执行temp = a[pos]而不是temp = x。

2. 有时内部循环永远不会进入if块。在那种情况下，to_swap的值将是不确定的（如果它发生在外循环的第一次迭代中），或更糟糕的是，它将是外循环的先前无关的迭代中具有的值。解决此问题的一种方法是在启动内部循环之前初始化to_swap = pos。

这些是使其生效所需的最少更改数量：

def SelectionSort(a):
    for m_index, x in enumerate(a[:-1]):
        pos = m_index
        # 1. Make sure to grab the value from the current array, not the original 
        temp = a[pos]
        print(temp, x)
        # 2. Make sure to always initialise to_swap again!
        to_swap = pos
        for index, y in enumerate(a[pos+1:]):
            if y < temp:
                temp = y
                to_swap = len(a) - len(a[pos+1:]) + index
        temp_var = a[to_swap]
        a[to_swap] = a[pos]
        a[pos] = temp_var
    return a

但是：

• 使用切片运算符（a[:-1]，a[pos+1:]）效率低下
• to_swap的更新归结为to_swap = pos + 1 + index
• 可以在没有临时变量的情况下进行交换：a[to_swap], a[pos] = a[pos], a[to_swap]

因此，这将是一个更好的实现：

def SelectionSort(a):
    for pos in range(0, len(a)-1):
        temp = a[pos]
        to_swap = pos
        for index in range(pos+1, len(a)):
            y = a[index]
            if y < temp:
                temp = y
                to_swap = index
        a[to_swap], a[pos] = a[pos], a[to_swap]
    return a