Python3：优化冒泡排序

Question

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

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

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

Answer 1

我想它已经优化了...... 朴素的冒泡排序不包括 swap 标志。因此在任何情况下它都不会 return 直到完成所有 O(n^2) 比较。但是有了swap标志，如果输入序列已经"almost sorted"，比较的次数将几乎是线性的。

Answer 2

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

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

Python3：优化冒泡排序

Python 3: Optimised Bubble Sort

python

algorithm

bubble-sort

python-3.x