鸡尾酒排序 | 算法必看系列十三

原文链接

鸡尾酒排序其实就是冒泡排序的变形，它的时间复杂度和冒泡排序一样，都是O(n^2)，比快速排序要慢不少。

鸡尾酒排序的思想有点像摆钟一样，从左到右，又从右到左。而冒泡排序只是单向执行。

鸡尾酒排序也是交换排序，假设做一个升序排序，先从左到右，交换一趟把最大的数放置右边，然后从右到左，把最小的数放置左边。

视频动画

Code

Result

优化 减少不必要的交换

看了前面冒泡排序和快速排序，我相信优化是一项学习的重点，以后面试中可以把这项说说来，展示出你的实力。

这次我们就优化不必要的交换次数，come on！

我么通过移除swap函数的调用，从而让程序运行的更快一点。每次进行符合条件判断时，不做交换，让最大或者最小的数据做一个标记，待全部比较完之后，才进行做交换。

视频动画

Code

Result

-----End-----

来源 | 算法无遗策
作者 | 我脱下短袖