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

oxalkeyp 于 2022-12-15 发布在 Python

关注(0)|答案(3)|浏览(150)

我开始学习 * 数据结构和算法，* 并试图实现冒泡排序：

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实现。上面的有什么问题吗？

python-3.x

来源：https://stackoverflow.com/questions/46017343/why-this-is-a-bad-bubble-sort-algorithm

3条答案

按热度按时间

y4ekin9u1#

几件事：
1.算法将不总是正确排序;
1.从句法上看，它似乎是以相反的方式排序;
1.则花费两倍于执行冒泡排序所需的时间量;
1.它 * 不是 * 泡沫排序;以及
1.你最好不要在Python中使用变量list，dict等等。

BubbeSort* 通过比较两个相邻元素进行排序：即所谓的“气泡”。如果检查左边的项是否确实小于右边的项。如果不是这样，则交换元素。该算法在列表上迭代最多 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 j in range(len(data)):  # iterate n times
        for i in range(len(data)-1-j):  # 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

但是使用冒泡排序是低效的--除了一些非常罕见的情况--最好使用更快的算法，如 QuickSort、MergeSort 和 TimSort（Python的内置排序算法）。

赞(0）回复(0）举报 2022-12-15

pkmbmrz72#

下面是实现bubble sort:的书籍的简短列表