视频动画 | 什么是鸡尾酒排序？

矫情吗；* 2023-06-23 02:47 61阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 算法无遗策

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

![format_png 1][]

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

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

视频动画

Code

![format_png 2][]

Result

初始状态 \[5, 1, 9, 3, 7, 4, 8, 6, 2\]

从左到右发生交换 \[1, 5, 9, 3, 7, 4, 8, 6, 2\]

从左到右发生交换 \[1, 5, 3, 9, 7, 4, 8, 6, 2\]

从左到右发生交换 \[1, 5, 3, 7, 9, 4, 8, 6, 2\]

从左到右发生交换 \[1, 5, 3, 7, 4, 9, 8, 6, 2\]

从左到右发生交换 \[1, 5, 3, 7, 4, 8, 9, 6, 2\]

从左到右发生交换 \[1, 5, 3, 7, 4, 8, 6, 9, 2\]

从左到右发生交换 \[1, 5, 3, 7, 4, 8, 6, 2, 9\]

从右到左发生交换 \[1, 5, 3, 7, 4, 8, 2, 6, 9\]

从右到左发生交换 \[1, 5, 3, 7, 4, 2, 8, 6, 9\]

从右到左发生交换 \[1, 5, 3, 7, 2, 4, 8, 6, 9\]

从右到左发生交换 \[1, 5, 3, 2, 7, 4, 8, 6, 9\]

从右到左发生交换 \[1, 5, 2, 3, 7, 4, 8, 6, 9\]

从右到左发生交换 \[1, 2, 5, 3, 7, 4, 8, 6, 9\]

从左到右发生交换 \[1, 2, 3, 5, 7, 4, 8, 6, 9\]

从左到右发生交换 \[1, 2, 3, 5, 4, 7, 8, 6, 9\]

从左到右发生交换 \[1, 2, 3, 5, 4, 7, 6, 8, 9\]

从右到左发生交换 \[1, 2, 3, 5, 4, 6, 7, 8, 9\]

从右到左发生交换 \[1, 2, 3, 4, 5, 6, 7, 8, 9\]

优化 减少不必要的交换

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

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

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

视频动画

Code

![format_png 3][]

Result

初始状态 \[5, 1, 9, 3, 7, 4, 8, 6, 2\]

从左到右发生交换 \[5, 1, 2, 3, 7, 4, 8, 6, 9\]

从右到左发生交换 \[1, 5, 2, 3, 7, 4, 8, 6, 9\]

从左到右发生交换 \[1, 5, 2, 3, 7, 4, 6, 8, 9\]

从右到左发生交换 \[1, 2, 5, 3, 7, 4, 6, 8, 9\]

从左到右发生交换 \[1, 2, 5, 3, 6, 4, 7, 8, 9\]

从右到左发生交换 \[1, 2, 3, 5, 6, 4, 7, 8, 9\]

从左到右发生交换 \[1, 2, 3, 5, 4, 6, 7, 8, 9\]

从右到左发生交换 \[1, 2, 3, 4, 5, 6, 7, 8, 9\]

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 4][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbURicWZRdWh5OGU5RTViOW91ME53aWFUTncxWmJXZGJXbzI0RzE0NnpzNTNRZ21EeU9NaWNVcmlhbUR0Yks5c1BPdkV0VWpRcGFTZVU2US82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbURicWZRdWh5OGU5RTViOW91ME53aWFORkFLZVRISlBIT29lMjV6WDRXNlJzSnZVUmh1MG5sTkg1VWpibG9oMUxtZk5pY0lpYlZ0UjVoQS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbURicWZRdWh5OGU5RTViOW91ME53aWFiRkcxVEM3Y2Z0c2J0WU9QZENqdHZnRmJ6MXc0VG9rSGdOenFzbW9QaWE2RmhodE1Ta1lBaWJody82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png