冒泡排序已排序列表

Question

如果传递给我的冒泡排序函数的列表已经被排序(或者已经被冒泡排序了一半)，我想停止它的运行。

我将冒泡排序函数定义为

def swap(values,i,j):
    values[i],values[j]=values[j],values[i]

def bubble(values):
    for i in range (len(values)-1):
        if values[i]>values[i+1]:
            swap(values,i,i+1)

def bubble_sort(values):
    count = 0
    for i in range(len(values)-1):
        count += 1
        bubble(values)
    return count

在这里，我计算了调用冒泡函数的次数，以查看执行了多少次交换。我想修改代码，以便在给定一个已经排序的列表时，bubble_sort()函数将停止调用bubble()函数。

我知道我将不得不在冒泡函数中使用一个布尔值，如果交换了任何值，它都会返回，但我不确定如何实际实现它。

Answer 1

正如Jorge在answer中显示的，但没有解释(如off jet)将一个布尔变量放入but中，默认值为True或False，无论您选择什么，如果您进行交换并在最后返回该变量，请将其值更改为oposite，如果您从but中获得的值是您的默认值，这意味着您的列表是按其他方式排序的，因此您必须继续调用该函数。然后，您可以将main函数更改为while循环，如下所示

def bubble(values):
    "return true if a swap was made, false otherwise" 
    flag = False
    for i in range(len(values)-1):
        if values[i]>values[i+1]:
            swap(values,i,i+1)
            flag = True
    return flag

def bubble_sort(values):
    count = 0 
    while bubble(values): # while there is a swap...
        count += 1
    return count 

测试

>>> test=[1,9,4,7,2,8,10,5,6,3]
>>> bubble_sort(test)
7
>>> test
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> bubble_sort(test)
0
>>> test
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> 

Answer 2

def swap(values,i,j):
    values[i],values[j]=values[j],values[i]

def bubble(values):
    flag = False
    for i in range (len(values)-1):
        if values[i]>values[i+1]:
            flag = True
            swap(values,i,i+1)
    return flag

def bubble_sort(values):
    count = 0
    for i in range(len(values)-1):
        count += 1
        if(not bubble(values))
            break
    return count