程序在选择排序算法中没有正确排序列表中的最低值

Question

我正在用 Python 编写一个程序，它实现了一个选择排序算法并按降序对列表的元素进行排序。

假设我的输入是l = [242, 18, 44, 201, 1111].

我的逻辑如下：

• l = [242, 18, 44, 201, 1111] # switch l[0] (242) and l[len(l)-1] (1111)

• l = [1111, 18, 44, 201, 242] # switch l[1] (18) and l[len(l)-1] (242)

• l = [1111, 242, 44, 201, 18] # switch l[2] (44) and l[len(l)-2] (201)

输出将是[1111, 242, 201, 44, 18].

所以，这是我基于上述逻辑实现的代码：

def selSort(l):

    '''Sorts the list in descending order using a selection sort algorithm.

    Params: l (list): unsorted list

    Sorts: unsorted list in descending order

    '''

    start = len(l)-1

    while start != 0:

        for i in range(len(l)):

            if l[i] < l[start]:

                l[i], l[start] = l[start], l[i]

        start -= 1

似乎我高估了我的逻辑，因为算法的输出是[1111, 18, 242, 201, 44].

经过一些调试，我能够发现在l正确排序了几次遍历之后，但是 while 循环仍然没有满足其终止条件。这意味着start和之间会有一些不需要的重叠i。例如， whenstart = 3和i = 4, l[i] < l[start]，导致l = [1111, 242, 201, 18, 44]。在额外的遍历之后，我们得到了我上面显示的错误输出。

这个问题的优雅（我知道选择排序不是最有效的算法）和 Pythonic 解决方案是什么？我试图在不使用任何内置函数（lenand除外range）、方法或外部库（如果可能）的情况下实现这一点。

我已经在 SO 上的Java帖子中查看了选择排序算法 Python和选择排序算法。前者使用列表方法（我试图避免使用），而我对 Java 语法的理解不够好，无法使用后者。

Answer 1

这应该有效。它还使用 range() 来避免使用 while 循环。def selSort(l):'''Sorts the list in descending order using a selection sort algorithm.Params: l (list): unsorted listSorts: unsorted list in descending order'''for i in range(len(l)):&nbsp; &nbsp; # Find the largest element in list&nbsp; &nbsp; max_index = i&nbsp; &nbsp; for j in range(i + 1, len(l)):&nbsp; &nbsp; &nbsp; &nbsp; if l[max_index] < l[j]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max_index = j&nbsp; &nbsp; # Swap the first and max item&nbsp; &nbsp; l[i], l[max_index] = l[max_index], l[i]

Answer 2

选择排序算法的逻辑（降序）：是对表进行 n-1 次迭代（n 是列表中的元素数）。在第 i 次迭代中，我们选择索引 i+1 和 n 之间的最高元素，并将该元素与列表中位置 i 的元素交换。这导致以下代码：def selSort(l):&nbsp; &nbsp; '''Sorts the list in descending order using a selection sort algorithm.&nbsp; &nbsp; Params: l (list): unsorted list&nbsp; &nbsp; Sorts: unsorted list in descending order&nbsp; &nbsp; '''&nbsp; &nbsp; for i in range(len(l)-1) :&nbsp; &nbsp; &nbsp; &nbsp; posMax = i&nbsp; &nbsp; &nbsp; &nbsp; for j in range(i+1,len(l)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if l[j] > l[posMax]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; posMax = j&nbsp; &nbsp; &nbsp; &nbsp; l[posMax], l[i] = l[i], l[posMax]&nbsp; &nbsp; return ll = selSort([242, 18, 44, 201, 1111])print(l) #prints [1111, 242, 201, 44, 18]