首页 文章

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

提问于
浏览 次
1

我正在用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上查看了Selection Sort Algorithm Python和Selection Sort Algorithm in Java帖子 . 前者使用list方法（我很好地理解java语法以利用后者 .

python python-3.x algorithm selection-sort

2 回答

  • 1

    选择排序算法的逻辑（降序）：是在表上迭代n-1次（n是列表中元素的数量） . 在第i次迭代中，我们选择索引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]
    回复于
  • 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]
    回复于

相关问题