高效冒泡排序作业

Question

我正在尝试以高效的方式进行冒泡排序。我有一个计数，它将我对函数 bubble 所做的所有调用相加。我需要找到一种使其高效的方法，如果调用 bubble 函数并且列表中没有值被交换，那么我不应该再次调用气泡函数。

我这里有包含三个函数的代码

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

def bubble(values):
    while True:
        swapped = False
        for i in range(len(values) - 1):
            if values[i] > values[i + 1]:
                swap(values, i, i+1)
                swapped = True
        if not swapped:
            break

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

test_1 = [1, 3, 67, 58, 91, 36, 100, 28, 90, 10, 57, 51, 52, 64, 56]
x = bubble_sort(test_1)
print(x, test_1)

test_2 = [2, 3, 4, 1, 5, 6, 7]
y = bubble_sort(test_2)
print(y, test_2)

当我尝试运行以下代码时，我得到的输出是：

14 [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100]

预期输出是：

8 [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100]

我以为编辑我的冒泡代码就可以解决问题，但即使我使用普通的冒泡排序函数也没有任何改变。

感谢任何帮助。谢谢。

Answer 1

您需要打破 bubble_sort 中调用 bubble 的外循环，以防没有交换。只需从 bubble 和 return 中删除 while 一个指示是否进行交换的布尔值。然后你可以在 bubble_sort 中停止 for 循环，如果你得到 False 作为 return 值：

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

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

    return swapped

通过这些修改，您将获得预期的输出：

(8, [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100])
(4, [1, 2, 3, 4, 5, 6, 7])

Answer 2

高效的冒泡排序。哈哈

一个简单的解决方法是让你的 bubble 函数 return False 如果它不执行任何交换。

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

然后，在您的 bubble_sort 函数中：

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

高效冒泡排序作业

Homework on bubble sorting efficiently

python

sorting

bubble-sort