冒泡排序BubbleSort

发表于 | 分类于 | 阅读次数 ℃
本文字数： 849 | 阅读时长 ≈ 1 分钟

想象一下鲤鱼吐泡泡的场景，一连串从小到大的泡泡从鲤鱼嘴边左摇右摆的浮到水面上（至少画画时是这么表示的。。。具体不曾考究）。冒泡排序和此场景类似，只是比场景多了一系列的比较过程。需要明确的有：

  • 因为要确定在这一堆泡泡中到底哪个才是最大的，这样才好让它最先浮上去。
  • 在寻找最大的泡泡过程中，只能两两相互比较 有了上面的约束，我们直接用代码看下冒泡排序的情况：
    1
    2
    3
    4
    5
    6
    def BubbleSort(arr):
        length = len(arr)
        for i in range(0, length):
            for j in range(0, length-i-1):
                if arr[j+1] < arr[j]:
                    arr[j+1], arr[j] = arr[j], arr[j+1]

这样，冒泡排序就很容易的实现了！
先不要高兴太早？想象有没有什么优化方法呢？

1
2
3
4
5
6
7
8
9
10
11
def BubbleSort(arr):
    length = len(arr)
    for i in range(0, length):
        is_swap = False # 此趟外循环是否发生数据交换的标识
        for j in range(0, length-i-1):
            if arr[j+1] < arr[j]:
                is_swap = True
                arr[j+1], arr[j] = arr[j], arr[j+1]
        # 如果没有发生数据交换，则说明整个数组已经都有序，故提前退出
        if not is_swap:
            break

通过上面的代码可以看出，冒泡排序的时间复杂度是O(n^2)，空间复杂度是O(1)，而且每趟排序都会保证至少一个数据处于它最终的位置上，并且后半部分先有序，前半部分后有序。