看到这个冒泡排序优化，还敢说不懂吗

vlambda
2021-08-04

看到这个冒泡排序优化，还敢说不懂吗

# 算法思想 #

对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。

0 1

原始冒泡

相邻元素比较，大数后沉小数前移。

看到这个冒泡排序优化，还敢说不懂吗

0 2

判断对象有序，提前结束循环

类似于：[9, 1, 2, 3, 4, 5, 6, 7, 8] 这样的部分有序待排序数组，使用原始冒泡发现除了第一次，之后均为无效操作。观察发现，当一次比较之后，如果没有发生交换行为，则认为该对象已经有序，便可提前结束循环。

看到这个冒泡排序优化，还敢说不懂吗

0 3

解'>'的耦合，扩大函数使用范围

类似于 {'Lucy'：20，'Hope':18, 'Anna':23, 'Tom':66} 的数据经过方式一优化的冒泡仍然不能适用。究其原因是由于判断时运算符耦合所引起的参数对象类型错误，通过隐函数的方式解耦合即可解决。（参数说明：*之前的为位置参数，之后的为命名关键字参数）

看到这个冒泡排序优化，还敢说不懂吗

0 4

创建函数对象，避免对调用函数对象的修改

观察Python内置的排序算法发现调用函数本身不对对象进行修改，而是返回一个重新生成的对象，保留调用函数的对象。故而通过切片操作实现函数对象的生成。

看到这个冒泡排序优化，还敢说不懂吗

0 5

双向比较，又称搅拌排序、鸡尾酒排序

类似于 [9, 2, 3, 4, 5, 6, 7, 8, 1] 这样的待排序对象，可以看出如果正向依次排序之后再反向进行相邻比较，只需要两次之后，第三次即可根据判断有无发生交换提前结束循环，大大减小了运算的时间。

看到这个冒泡排序优化，还敢说不懂吗

# 简单排序 #

时间复杂度为O(N**2)的排序算法中对冒泡排序面试面的最多，大概就是冒泡算法容易优化吧！而且优化之后也是相当便捷的。

作者丨GHope

https://www.jianshu.com/p/f74fdcb2aa0c

我知道你在看哦

往期精彩回顾

vlambda博客
学习文章列表