gpt4 book ai didi

python 3 : Optimised Bubble Sort

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:19:33 24 4
gpt4 key购买 nike

请帮忙。我需要优化我的冒泡排序算法,以便获得比未优化的冒泡排序更少的总比较。我设法只创建了“普通冒泡排序”(仅从左到右行进):

def bubbleSort(values):
n = len(values) - 1
swap = True
ncomp = 0 # My total comparisons counter
while swap:
swap = False
for i in range(n): # i = 0, 1, 2, ..., n-1
ncomp += 1
if values[i] > values[i+1]:
temp = values[i]
values[i] = values[i+1]
values[i+1] = temp
swap = True
return values, ncomp

所以基本上我不知道如何创建一个“优化的 bubbleSort”,一个 bubbleSortPlus 函数,其中气泡在两个方向上移动:从左到右,紧接着是从右到左的移动。理论上,在每次通过时,气泡的行程都应该缩短(在变量中保存行程中最后一次交换的位置,并使下一次行程从该位置开始。我很努力但我只是一条 python 新手,请帮助。

最佳答案

下面是一些框架代码,展示了如何向前和向后扫描数组,同时在每次迭代时缩小列表。

values = 100,101,102,103,104,105

start = 0
stop = len(values)-1

while stop > start:
for i in range(start, stop):
print i, "compare", values[i], "with", values[i+1]
print "moved a large value to index", stop
print

stop = stop - 1
if stop == start:
break

for i in range(stop, start, -1):
print i, "compare", values[i], "with", values[i-1]
print "moved a small value to index", start
print

start = start + 1

关于 python 3 : Optimised Bubble Sort,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37288908/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com