动画：什么是鸡尾酒排序和地精排序？
总第60篇/程序员小吴
从冒泡排序开始
先来看回顾一下冒泡排序的思想和原理。
冒泡排序的思想
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。
冒泡排序算法的原理
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
一般情况下，可以通过下面的动画理解冒泡排序。
现在我们来看一组特殊数据如果使用冒泡排序会怎么样。
将无序数列：2，3，4，5，6，7，8，1，使用冒泡排序使其从小到大排序。
进行逐步分析：
第一轮操作（ 8 和 1 交换 ）
第一轮操作（ 8 和 1 交换 ） 第二轮操作（ 7 和 1 交换 ）
第二轮操作（ 7 和 1 交换 ） 第三轮操作（ 6 和 1 交换 ）
第三轮操作（ 6 和 1 交换 ） 第四轮操作（ 5 和 1 交换 ）
第四轮操作（ 5 和 1 交换 ） 第五轮操作（ 4 和 1 交换 ）
第五轮操作（ 4 和 1 交换 ） 第六轮操作（ 3 和 1 交换 ）
第六轮操作（ 3 和 1 交换 ） 第七轮操作（ 2 和 1 交换 ）
第七轮操作（ 2 和 1 交换 ）
仔细观察上面的这组无序数列，实际上只有 1 的位置不在该在的位置，而 2 ，3 ，4 ，5 ，6 ，7 ，8 都已经有序了，结果使用冒泡排序，需要 折腾 7 次 才能将 1 归位。
鸡尾酒排序
鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
排序过程：
先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端
再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端
以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束
Show Me The Animation
第一轮操作（ 8 和 1 交换 ）
第一轮操作（ 8 和 1 交换 ） 第二轮操作 ( 从序列右边开始遍历 ）
第二轮操作 ( 从序列右边开始遍历 ） 第三轮操作 ( 从左向右比较和交换 )
第三轮操作 ( 从左向右比较和交换 )
在这一轮操作中，没有元素位置交换，证明已经有序，排序结束。
对比 冒泡排序 ，鸡尾酒排序只需要 3 轮操作就可以完成排序。
地精排序
Gnome 排序（地精排序），起初由 Hamid Sarbazi-Azad 于 2000 年提出，并被称为 stupid 排序，后来被 Dick Grune 描述并命名为 “地精排序” 。
地精排序和插入排序类似，除了移动一个元素到最终的位置，是通过交换一系列的元素实现，就像冒泡排序一样。概念上十分简单，不需要嵌套循环。时间复杂度为O(n^2)，但是如果初始数列基本有序，时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。平均运行时间为O(n^2)。
将无序数列：6，2，4，1，5，使用地精排序使其从小到大排序。
通过设计标识 i = 0 ，然后从头开始判断，什么时候 ( i < 4 ) 不成立,什么时候排序结束。
这里的核心点就是 如何控制 i 的值。
第一轮操作「i = 0」
先让 i 自增 1 ，达到值为 1 才开始比较 ：
交换前 [ 6 2 4 1 ] 『 i = 0 』
交换后 [ 6 2 4 1 ] 『 i = 1 』
第二轮操作「i = 1」
比较 6 和 2 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 6 2 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 0 』
第三轮操作「i = 0」
i 变成 0 了，啥也不干，自增变成 1 再说。
交换前 [ 2 6 4 1 ]『 i = 0 』
交换后 [ 2 6 4 1 ]『 i = 1 』
第四轮操作「i = 1」
比较 2 和 6 ，不交换，只要不要换就自增 1。
交换前 [ 2 6 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 2 』
第五轮操作「i = 2」
比较 6 和 4 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 6 4 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 1 』
第六轮操作「i = 1」
比较 2 和 4 ，不交换，只要不要换就自增 1 。
交换前 [ 2 6 4 1 ]『 i = 1 』
交换后 [ 2 4 6 1 ]『 i = 2 』
第七轮操作「i = 2」
比较 4 和 6 ，不交换，只要不要换就自增 1 。
交换前 [ 2 4 6 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 3 』
第八轮操作「i = 3」
比较 6 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 4 6 1 ]『 i = 3 』
交换后 [ 2 4 1 6 ]『 i = 2 』
第九轮操作「i = 2」
比较 4 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 4 1 6 ]『 i = 2 』
交换后 [ 2 1 4 6 ]『 i = 1 』
第十轮操作「i = 1」
比较 2 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 1 4 6 ]『 i = 1 』
交换后 [ 1 2 4 6 ]『 i = 0 』
第十一轮操作「i = 0」
啥也不干，先让 i 自增1，达到值为 1 才开始真正的比较。
『 i = 1 』时，比较 1 和 2 ，不交换，只要不交换就自增 1 。
『 i = 2 』时，比较 2 和 4 ，不交换，只要不交换就自增 1 。
『 i = 3 』时，比较 4 和 6 ，不交换，只要不交换就自增 1 。
『 i = 4 』时，表达式 （ i < n ) 不成立，排序结束。
顺序输出为 [ 1 2 4 6 ]。
地精排序算法代码
1template <class T>
2void gnome_sort_1(T data[], int n, bool comparator(T, T)){
3 int i = 1;
4 while (i < n){
5 if (i > 0 && comparator(data[i], data[i-1])){
6 swap(data[i], data[i-1]);
7 i--;
8 }else{
9 i++;
10 }
11 }
12}
这种地精排序算法还有很多优化的空间，这里小吴就不展开来讲了。
End
鸡尾酒排序和地精排序虽然被程序员小吴归为奇葩排序一类，但是它们还是有一定的使用场景的。
在「大部分元素有序」的情况下，使用鸡尾酒排序可以减少排序的回合数。
地精排序最著名的特点是代码只有一层循环，在「大部分元素有序」的情况下，可以减少排序回合数。
掏空小吴计划
/ 今日问题 /
除了鸡尾酒排序和地精排序以外，你还知道哪些排序适合用于「大部分元素有序」的序列进行排序？
留言格式 —— Day xx : blablabla 这里再强调下 ，不符合主题和格式的打卡无效噢 ！不要到兑换的时候尴尬呀！小吴已经开始在excel表格一个个整理了噢，后续考虑透明化打卡。无效的留言目前小吴还是一个个回复说了无效，今后不说了，不精选就是无效！毕竟有效留言也可以相互学习啊，你说呢？
补充一些话：小吴是一名在职的一线程序员，白天要在公司写很多bug（逃），所以公众号的所有文章都是小吴晚上和周末在家写的，而且为了将动画做的更加简单明了，小吴耗费了大量的时间进行调试，所以一篇文章基本上要两到三天才能写完。小吴现在搞了这个 掏空小吴计划 ，最主要的原因是 希望通过互动的方式能让我的读者们认真的看文章，通过看我写的文字和制作的动画在碎片时间里也能掌握一点知识。
如果读者能通过我写的文字有所收获，那我真是太开心了，当然如果点点好看，点点AD那就更开心了：）
往期推荐：
这些奇葩的排序算法，你没见过动画吧？
欢迎关注这个会做动画的程序员👆