这是我的代码 - 用于按升序对列表元素进行排序的冒泡排序算法:
foo = [7, 0, 3, 4, -1]
cnt = 0
for i in foo:
for i in range(len(foo)-1):
if foo[cnt] > foo[cnt + 1]:
temp = foo[cnt]
c[cnt] = c[cnt + 1]
c[cnt + 1] = temp
cnt = cnt + 1
cnt = 0
我一直在修改我的代码,但对于在线判断来说仍然太低效。一些帮助将不胜感激!
提前退出冒泡排序
- 第一个循环与内部发生的情况无关
- 第二个循环完成所有繁重的工作。你可以摆脱
count
通过使用enumerate
- 要交换元素,请使用 pythonic swap -
a, b = b, a
.
- As per 这条评论,利用提前退出的机会。如果内部循环中的任何点都没有进行交换,则意味着列表已排序,并且不需要进一步迭代。这就是背后的直觉
changed
.
- By definition, after the ith iteration of the outer loop, the last
i
elements will have been sorted, so you can further reduce the constant factor associated with the algorithm.
foo = [7, 0, 3, 4, -1]
for i in range(len(foo)):
changed = False
for j, x in enumerate(foo[:-i-1]):
if x > foo[j + 1]:
foo[j], foo[j + 1] = foo[j + 1], foo[j]
changed = True
if not changed:
break
print(foo)
[-1, 0, 3, 4, 7]
请注意,这些优化都没有改变冒泡排序的渐近(Big-O)复杂性(仍然存在)O(N ** 2)
),相反,仅减少相关的常数因子。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)