[数据结构与算法]冒泡排序算法

冒泡排序算法是算法与数据结构中最基础的排序算法。学会这个算法是有必要，在2010年左右的时候，很多时候面试都会冒泡排序算法。那时候IT行业没现在这么卷，大部分都考察一下冒泡排序就OK了。现在去面试不问个leetcode的hard难度的级别题都不过瘾。那现在有必须在学习冒泡排序吗？当然有必要，基础算法必须掌握，体现你的技术热情，对走技术路线是有绝对的帮助的。

冒泡排序就是排队一样，矮的排前面，高的排后面。?

刚开始是乱序的，那就从第一个开始调整，把最高排到后面。排完这个之后，这个位置就被占用。

那再从第一个开始，再找出一个最高的放在倒数第二个位置。

周而复始一直到第一个位置确定好。

发现没有，每个最高的放在最后，然后缩小数组范围，再找出一个高的放在最后。

关键点：?

每次都从第一个开始，写代码的时候要注意。

一趟比较后，最后那个位置放最大的数。

除去最后一个位置，再走一趟比较放到倒数第二位置。与第一趟是?一样的，只是范围变窄了。

冒泡排序是稳定的排序， 时间复杂度是o(n^2)

看一个简单例子：

5， 3， 2， 1 一趟冒泡如何进行

第一次比较 ：5,? 3, 2, 1 ；5和3需要调换位置 ：? 3,? 5, 2, 1 ；?

第二次比较 ：3,??5, 2, 1 ；? 5和2需要调换位置 ：? 3, 2, 5, 1 ；?

第三次比较 ：3, ?2, 5, 1 ；? 5和1需要调换位置 ：? 3, 2, 1, 5 ；?

第一趟排序后，5就到最后的位置。

下面我们一下代码的实现：

def bub_sort(elements):

n = len(elements)

for i in range(n):

#注意在这里一趟排序后，缩小范围了

for j in range(0, n - i - 1):

if elements[j] > elements[j + 1]:

elements[j], elements[j + 1] = elements[j + 1], elements[j]

if __name__ == '__main__':

arr = [5, 2, 3, 1]

bub_sort(arr)

print(arr)

运行后输出结果：

[1, 2, 3, 5]