为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

小唯快跑啊 2021-09-11 15:53:17
我正在用 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 语法的理解不够好,无法使用后者。
查看完整描述

2 回答

?
慕无忌1623718

TA贡献1744条经验 获得超4个赞

这应该有效。它还使用 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]


查看完整回答
反对 回复 2021-09-11
?
绝地无双

TA贡献1946条经验 获得超4个赞

选择排序算法的逻辑(降序):是对表进行 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]


查看完整回答
反对 回复 2021-09-11
  • 2 回答
  • 0 关注
  • 166 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
微信客服

购课补贴
联系客服咨询优惠详情

帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

公众号

扫描二维码
关注慕课网微信公众号