冒泡排序

1、题目

假设有一个列表 list = [5,4,3,2,1]

要求：按从小到大的顺序排序

2、分析

● 冒泡排序的思路

两两比较，互换位置，每一轮选出最大（小）的数放到列尾

● 图解

① 第一轮比较

第一轮比较

② 第二轮比较

③ 第三轮比较

④ 第四轮比较

由于每一轮只选出 1 个最大数，当最后一轮只剩 2 个元素时，结束。

总共需要比较的轮数 = 列数 - 1

比较的次数 = 列元素的个数 - 1，由于每一轮会排除一个最大（小）数，比较的次数会依次减 1；

3、Python 方案

● Python 代码：

● Python 结果：

4、冒泡排序的时间复杂度

从代码中可以看出一共遍历了

n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，

那么时间复杂度是 O (N^2)。

5、冒泡排序优化

曾经，Python大星 参加一个面试，面试官突然给我一张纸和笔，让我现场写个冒泡排序。

so easy，冒泡排序是排序算法中最简单的一个，三下五除二，我就交上答卷。面试官点了点头，示意我的答案正确，但接下来问了我一个问题，就让我回家等消息啦。

OS：冒泡排序还能优化？？？

例如：无序列表为[2,3,1,4,5]

按照之前的冒泡排序的逻辑：该列表需要进行 4 轮排序

但我们可以观察到：

● 在第二轮排序后，整个列表已经达到要求了，后面的循环无意义

优化点：当第 N 轮 无元素交换位置，则退出循环

第一轮排序过程

第二轮排序过程

● 在第一轮后，我们可以观察到只进行了一次交换，从 3 后的数字已经排好序，故第二轮的比较中，再比较3之后的数字没有意义

优化点：找出每轮排序的边界

优化代码：

>>>

閱讀更多 Python大星 的文章

關鍵字: 算法 操作系统 面试