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

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 之间会有一些不需要的重叠。例如，当 start = 3 和 i = 4、l[i] < l[start] 时，结果是 l = [1111, 242, 201, 18, 44]。经过额外的遍历，我们得到了上面显示的错误输出。

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

我已经在 SO 上查看了 and 的帖子。前者使用列表方法（我试图避免），我对 java 语法的理解不够好，无法使用后者。

Answer 1

这应该有效。它还使用 range() 来避免必须使用 while 循环。

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
'''
for i in range(len(l)):

    # Find the largest element in list
    max_index = i
    for j in range(i + 1, len(l)):
        if l[max_index] < l[j]:
            max_index = j

    # Swap the first and max item
    l[i], l[max_index] = l[max_index], l[i]

Answer 2

select 排序算法（降序）的逻辑：是迭代table n-1 次（n 是列表中元素的数量）。在第 i 次迭代中，我们 select 索引 i+1 和 n 之间的最高元素，并将该元素与列表中位置 i 处的元素交换。这导致以下代码：

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
    '''
    for i in range(len(l)-1) :
        posMax = i
        for j in range(i+1,len(l)):
            if l[j] > l[posMax]:
                posMax = j
        l[posMax], l[i] = l[i], l[posMax]
    return l

l = selSort([242, 18, 44, 201, 1111])
print(l) #prints [1111, 242, 201, 44, 18]

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

Program does not properly sort lowest value in list in selection sort algorithm

python

python-3.x

algorithm

selection-sort