冒泡排序

概念和图示

冒泡排序(Bubble sort) 的概念如下:

1. 循环访问数组, 一次比较两个元素.
2. 比较后(假设是从小到大排序), 最小的元素放到最左边.
3. 重复循环

现在网上有很多演示算法的动画, 例如这是一个不错的网址: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

问题是, 算法都是由若干大步骤+小步骤组成, 这些图只是演示了大步骤, 所以我觉得其实自己画图一遍更容易记忆, 灵魂画手上线:

gaitubao_Selection_075.png

红色表示循环时候的数组索引i所对应的值. 可以看到它不断地和邻居进行比较.

算法效率

假设数列本身就已经是正确排序, 那么操作只需要O(n)
假设数列本身没有排序, 那么操作是O(n²)

所以算法的效率是: O(n) <= 冒泡 <= O(n²)

代码

#! /usr/bin/python
# -*- coding: UTF-8 -*-

"""

    作者: 小肥巴巴
    简书: https://www.jianshu.com/u/db796a501972
    邮箱: imyunshi@163.com
    github: https://github.com/xiaofeipapa/algo_example

    您可以任意转载, 恳请保留我作为原作者, 谢谢.

"""


def exchange_value(data_list, index, index_plus_one):

    temp = data_list[index]
    data_list[index] = data_list[index_plus_one]
    data_list[index_plus_one] = temp


def bubble_sort(data_list, sort='asc'):

    # sort 是 asc (从小到大) 或者 desc (从大到小)

    size = len(data_list)

    for i in range(0, size):

        for j in range(0, size):

            # 已经是最后一位
            if j == size - 1:
                break

            # 如果是升值排序
            if sort == 'asc' and data_list[j] > data_list[j+1]:
                exchange_value(data_list, j, j+1)

            # 如果是降序
            if sort == 'desc' and data_list[j] < data_list[j+1]:
                exchange_value(data_list, j, j+1)


def test_it():

    data_list = [5, 4, 10, 2, 7]
    bubble_sort(data_list)
    print('==== 排序后: ', data_list)

    data_list = [5, 4, 10, 2, 7]
    bubble_sort(data_list, 'desc')
    print('==== 排序后: ', data_list)


if __name__ == '__main__':
    test_it()

怎么记忆

为了方便记忆, 继续歪诗一首:

邻居走访, 社区和睦. 

根据相邻交换值这个原则来记, 错不了.