python - 在 Python 中进行优化的冒泡排序

Question

我是 Python 的新手，我开始学习排序算法、PEP8 和 Python 之禅。我刚刚在 CodeReview 上写了一篇文章.我做了修复，我想问一下 Optimizing Bubble Sort : Second option .我实现了优化冒泡排序的第一个选项，但我对第二个选项有疑问。维基百科中“允许我们跳过很多元素，导致比较计数在最坏情况下提高 50%”的那个。所以我的第一个选项的代码看起来像并且有效:

def bubble_sort(container):
    """
        Bubble sort with optimization.

        Description
        ----------
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        data_container : Mutable structure with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        None

        Examples
        ----------
        >>> bubble_sort([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    length = len(container)
    changed = True

    while changed:
        changed = False
        for i in range(length - 1):
            if container[i] > container[i + 1]:
                container[i], container[i + 1] = container[i + 1], container[i]
                changed = True
        length -= 1

问题是我必须进行哪些更改才能实现第二个优化选项。此外，到目前为止，我已经尝试过在伪代码中表现得像。我的代码没有工作(没有排序)并且看起来像:

# setting up variables
length = len(container)

while length >= 1:
    number_of_changed = 0
    for i in range(1, length - 1):
        if container[i-1] > container[i]:
            container[i-1], container[i] = container[i], container[i-1]
            number_of_changed = i
    length = number_of_changed

Answer 1

container = [7,1,2,6,4,2,3]
length = len(container)

while length >= 1:
    num = 0
    for i in range(1, length):
        if container[i-1] > container[i]:
            container[i-1], container[i] = container[i], container[i-1]
            num = i
            print(num,'\n')
    length = num
    print(container)

我看到的问题是，您将范围设置为从 1 到 (length - 1) -> (7-1)，即 6，因此它将转到数组中的第 6 个元素。因此，从 for 循环的长度中减去负 1，它应该可以解决问题。尝试将 print 放在您认为可能导致问题的地方，它将帮助您调试程序并告诉您需要的信息。希望这会有所帮助。