python - 为什么这是一个糟糕的冒泡排序算法？

Question

我开始研究数据结构和算法，并尝试实现冒泡排序:

def BubbleSort(list):
    for a in range(len(list)): 
      for b in range(len(list)):# I could start this loop from 1
        if list[a]< list[b]:   # to avoid comparing the first element twice
          temp=list[a]
          list[a]=list[b]
          list[b]=temp
    return list

我浏览了网络和书籍 - 但没有发现冒泡排序的 Python 实现。 以上有什么问题吗？

Answer 1

几件事:

1. 算法并不总是正确排序；
2. 在句法上它似乎以相反的方式排序；
3. 执行冒泡排序所需的时间是执行时间的两倍；
4. 它不是冒泡排序；和
5. 最好不要在 Python 中使用名为 list、dict 等的变量。

BubbeSort 通过比较两个相邻 元素进行排序:即所谓的“气泡”。 If 检查左边的项目是否确实小于右边的项目。如果不是这种情况，它会交换元素。该算法对列表最多迭代 n 次，之后保证对其进行排序。

所以一个非常基本的实现是:

def BubbleSort(data):
    for _ in range(len(data)):  # iterate n times
        for i in range(len(data)-1):  # i is the left index of the bubble
            if data[i+1] > data[i]:  # if the left item is greater
                # perform a swap
                temp = data[i]
                data[i] = data[i+1]
                data[i+1] = temp
    return data

现在我们可以通过在 len(data)-1-j 停止来改进算法(大约让算法用一半的时间工作)，因为在每次迭代之后，最右边的元素气泡已经移动保证是最大的:

def BubbleSort(data):
    for <b>j</b> in range(len(data)):  # iterate n times
        for i in range(len(data)-1<b>-j</b>):  # i is the left index of the bubble
            if data[i+1] > data[i]:  # if the left item is greater
                # perform a swap
                temp = data[i]
                data[i] = data[i+1]
                data[i+1] = temp
    return data

但是使用 bubblesort 是——除了一些非常罕见的情况——效率低下。最好使用更快的算法，例如 QuickSort、MergeSort 和 TimSort(Python 的内置排序算法)。