数据结构（2）冒泡排序+Python

利用Python实现数据结构中的冒泡排序。

运行平台： Windows
Python版本： Python 3.8
IDE： Pycharm

概念

       冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

2. 针对所有的元素重复以上的步骤，除了最后一个。

3. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实现一次冒泡的算法

       实现一次冒泡排序的代码和结果

def bubble_sort(alist):
    n = len(alist)
    for i in range(n - 1):
        if alist[i] > alist[i + 1]:
            alist[i], alist[i + 1] = alist[i + 1], alist[i]
    return alist


list = [5, 4, 1, 2, 0, 3]
print(bubble_sort(list))
#结果：
[4, 1, 2, 0, 3, 5]

普通冒泡排序算法

       刚刚我们只实现了一次冒泡排序，我们可以在以上的基础上进行改进。通过再嵌套1层循环来实现冒泡，第一层for循环控制冒泡的次数，第二层for循环控制相邻两个元素比较的次数。

def bubble_sort_1(alist):
    n = len(alist)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
    return alist


list = [5, 4, 1, 2, 0, 3]
print(bubble_sort_1(list))
#结果：
[0, 1, 2, 3, 4, 5]

优化的冒泡排序算法

       普通的冒泡排序算法在遇到[5, 1, 2, 3, 4]类似这些情况时，即使只需要冒泡1次即可完成时，还是需要4次冒泡才能完成。
       所以为了解决这个问题，引入1个count记录需要交换的次数，当count==0时就代表前面的元素已经是有序的了，就可以直接返回了。

def bubble_sort_2(alist):
    n = len(alist)
    for i in range(n - 1):
        count = 0
        for j in range(n - i - 1):
            if alist[j] > alist[j + 1]:
                count += 1
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
        if count == 0:
            return alist


list = [5, 4, 1, 2, 0, 3]
print(bubble_sort_2(list))
#结果：
[0, 1, 2, 3, 4, 5]

总结

• 时间复杂度：O(n^2)
• 稳定性：稳定