【算法】冒泡排序 Bubble Sort

算法介绍

冒泡算法源于水中气泡变化，以升序排序为例，从第一个元素开始，依次比较相邻两个元素的大小，将大的数放在后面；扫描一遍后，最大的数就被放在了最后面；然后进行第二轮扫描，将第二大的数放在倒数第二的位置上；一直重复扫描 n-1 遍。

视频演示

视频地址：https://www.bilibili.com/video/av18176281

python代码

# -*- coding: utf-8 -*-

# 升序
def bubble_sort(data):
    n = len(data)
    # 外循环， i 代表扫描轮数，一共扫描 n-1 轮
    for i in range(n-1):
        # 内循环，第 i 轮，扫描前 n-i 个数
        for j in range(1, n-i):
            if data[j]>data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
    return data


if __name__ == '__main__':
    data = [5, 1, 4, 2, 8, 9]
    sorted_data = bubble_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

无论真实数据如何，比较次数固定为：n*(n-1)/2。

最好情况下，数据刚好是升序的，不需要交换数据；
最坏情况下，数据刚好是降序的，每次比较都需要交换数据，即交换数据次数为：n*(n-1)/2。

冒泡排序时间复杂度为：O(n^2)

冒泡排序空间复杂度为：O(1)