冒泡排序
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之后的数字没有意义
优化点:找出每轮排序的边界
优化代码:
>>>