程序员须掌握的数据结构：冒泡排序python代码实现

冒泡排序，时间复杂度O(n^2)，冒泡排序通常被认为是低效的排序方式。优势是：识别排序列表，和提前终止排序。短冒泡排序就是提前终止的冒泡排序。冒泡排序4行，短冒泡排序8行。

# 源码: https://github.com/SpikeKing/data_structure_with_python
def bubble_sort(alist):
    """
    冒泡排序
    1. 两次遍历，第1次遍历长度，倒序逐渐减1，每遍历一次，排序一个；
    2. 第2次，正常遍历，少1个值，因为i和i+1；
    3. 当前位大于下一位，交换当前位和下一位；
    4. 4行
    :param alist: 待排序列表
    :return: None，内部排序
    """
    for p_num in range(len(alist) - 1, 0, -1):
        for i in range(p_num):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]


def bubble_sort_short(alist):
    """
    短冒泡排序，增加exchange，额外终止参数
    1. 初始为True，当为False时终止；
    2. 在第2次循环前，设置为False，交换一次就设置为True，一次未交换则触发终止；
    3. 8行，增加5行的exchange操作
    :param alist:
    :return:
    """
    for p_num in range(len(alist) - 1, 0, -1):
        exchange = False
        for i in range(p_num):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                exchange = True
        if not exchange:
            # print('提前终止')
            return

                
def test_of_bubble_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # bubble_sort(alist)
    # print(alist)
    alist = [17, 20, 26, 93, 77, 31, 44, 55, 54]
    short_bubble_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_bubble_sort()