python - 程序在选择排序算法中没有正确排序列表中的最小值
问题描述
我正在用 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
and除外range
)、方法或外部库(如果可能的话)的情况下实现这一点。
我已经在 SO 上查看了选择排序算法 Python和Java 中的选择排序算法。前者使用列表方法(我试图避免),而我对 java 语法的理解不够好,无法使用后者。
解决方案
这应该有效。它还使用 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]
推荐阅读
- database - 为什么 Liquibase generateChangeLog 会生成一个空的 changelog 文件?
- javascript - 如何将外部 js 文件添加到我的布局页面
- javascript - 使用 Cloudflare Workers 将图像发送到 Telegram
- java - 如何成功导入包含所有依赖项的 AndroidX 包?
- c# - 无法使用 WordPressPCL 和 wp-api-jwt-auth 对 Linux 中托管在 Azure 中的 WordPress 进行身份验证
- performance - 了解 WebPageTest 瀑布
- python - 具有三向决胜局的 Python 高效排序算法
- java - 如何使所有实现特定接口的类都具有相同的构造函数?
- ios - 碰撞处理在 iOS 13 中不起作用
- python - 如何显示电话簿的详细视图?