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

算法原理

比较相邻的元素,如果第一个比第二个大,就交换他们;

对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

针对所有的元素重复以上步骤,除了最后一个;

重复步骤 1~3,直到排序完成。

图解

9916080-f0605d250bd43468.gif

复杂度分析

最坏复杂度: 时间复杂度为 O(n^2)

最好复杂度:时间复杂度为 O(n)

平均复杂度: 时间复杂度为 O(n^2)

def bubble_sort(sequence):
    for i in range(1, len(sequence)):
        for j in range(0, len(sequence)-i):
            if sequence[j] > sequence[j+1]:
                sequence[j], sequence[j+1] = sequence[j+1], sequence[j]
            print(sequence)
    return sequence

if __name__ == '__main__':
    sequence = [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    print(sequence)
    print(bubble_sort(sequence))