动画：什么是鸡尾酒排序和地精排序？

偏执的太偏执、 2021-09-29 10:54 471阅读 0赞

奇葩排序第二弹：）

### 从冒泡排序开始 ###

先来看回顾一下冒泡排序的思想和原理。

#### 冒泡排序的思想 ####

冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

#### 冒泡排序算法的原理 ####

*  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

一般情况下，可以通过下面的动画理解冒泡排序。

![冒泡排序][1683a569b8f9419f_w_954_h_537_f_gif_s_906068]冒泡排序

现在我们来看一组特殊数据如果使用冒泡排序会怎么样。

将无序数列：2，3，4，5，6，7，8，1，使用冒泡排序使其从小到大排序。

![无序数列][1683a569b9213adb_w_1706_h_308_f_png_s_26112]无序数列

进行逐步分析：

1.  第一轮操作（ 8 和 1 交换 ）  
    ![第一轮操作（ 8 和 1 交换 ）][8 _ 1 _]第一轮操作（ 8 和 1 交换 ）
2.  第二轮操作（ 7 和 1 交换 ）  
    ![第二轮操作（ 7 和 1 交换 ）][7 _ 1 _]第二轮操作（ 7 和 1 交换 ）
3.  第三轮操作（ 6 和 1 交换 ）  
    ![第三轮操作（ 6 和 1 交换 ）][6 _ 1 _]第三轮操作（ 6 和 1 交换 ）
4.  第四轮操作（ 5 和 1 交换 ）  
    ![第四轮操作（ 5 和 1 交换 ）][5 _ 1 _]第四轮操作（ 5 和 1 交换 ）
5.  第五轮操作（ 4 和 1 交换 ）  
    ![第五轮操作（ 4 和 1 交换 ）][4 _ 1 _]第五轮操作（ 4 和 1 交换 ）
6.  第六轮操作（ 3 和 1 交换 ）  
    ![第六轮操作（ 3 和 1 交换 ）][3 _ 1 _]第六轮操作（ 3 和 1 交换 ）
7.  第七轮操作（ 2 和 1 交换 ）  
    ![第七轮操作（ 2 和 1 交换 ）][2 _ 1 _]第七轮操作（ 2 和 1 交换 ）

仔细观察上面的这组无序数列，实际上只有 1 的位置不在该在的位置，而 2 ，3 ，4 ，5 ，6 ，7 ，8 都已经有序了，结果使用冒泡排序，需要 **折腾 7 次** 才能将 1 归位。

### 鸡尾酒排序 ###

![鸡尾酒排序][1683a569ef8b3ade_w_277_h_257_f_gif_s_900082]鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。

**此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。**

排序过程：

*  先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端
 *  再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端
 *  以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束

**Show Me The Animation**

1.  第一轮操作（ 8 和 1 交换 ）  
    ![第一轮操作（ 8 和 1 交换 ）][8 _ 1 _ 1]第一轮操作（ 8 和 1 交换 ）
2.  第二轮操作 ( 从序列右边开始遍历 ）  
    ![第二轮操作 ( 从序列右边开始遍历 ）][_ _]第二轮操作 ( 从序列右边开始遍历 ）
3.  第三轮操作 ( 从左向右比较和交换 )  
    ![第三轮操作 ( 从左向右比较和交换 )][_ _ 1]第三轮操作 ( 从左向右比较和交换 )  
    在这一轮操作中，没有元素位置交换，证明已经有序，排序结束。

对比 冒泡排序 ，鸡尾酒排序只需要 3 轮操作就可以完成排序。

### 地精排序 ###

> Gnome 排序（地精排序），起初由 Hamid Sarbazi-Azad 于 2000 年提出，并被称为 **stupid** 排序，后来被 Dick Grune 描述并命名为 “地精排序” 。

地精排序和插入排序类似，除了移动一个元素到最终的位置，是通过交换一系列的元素实现，就像冒泡排序一样。概念上十分简单，不需要嵌套循环。时间复杂度为O(n2)，但是如果初始数列基本有序，时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。平均运行时间为O(n^2)。

将无序数列：6，2，4，1，5，使用地精排序使其从小到大排序。

通过设计标识 i = 0 ，然后从头开始判断，什么时候 ( i < 4 ) 不成立,什么时候排序结束。

这里的核心点就是 **如何控制 i 的值**。

#### 第一轮操作「i = 0」 ####

![1683a56a2dd5946a_w_849_h_284_f_gif_s_22189][]

先让 i 自增 1 ，达到值为 1 才开始比较 ：

交换前 \[ 6 2 4 1 \] 『 **i = 0** 』

交换后 \[ 6 2 4 1 \] 『 **i = 1** 』

#### 第二轮操作「i = 1」 ####

![1683a56a2f974af7_w_849_h_284_f_gif_s_60337][]

比较 6 和 2 ，发生交换，**只要发生交换 i 就减 1** 。

交换前 \[ 6 2 4 1 \]『 i = 1 』

交换后 \[ 2 6 4 1 \]『 i = 0 』

#### 第三轮操作「i = 0」 ####

![1683a56a472e0671_w_849_h_284_f_gif_s_35838][]

i 变成 0 了，啥也不干，自增变成 1 再说。

交换前 \[ 2 6 4 1 \]『 i = 0 』

交换后 \[ 2 6 4 1 \]『 i = 1 』

#### 第四轮操作「i = 1」 ####

![1683a56a45323fb0_w_849_h_284_f_gif_s_39303][]

比较 2 和 6 ，不交换，**只要不要换就自增 1**。

交换前 \[ 2 6 4 1 \]『 i = 1 』

交换后 \[ 2 6 4 1 \]『 i = 2 』

#### 第五轮操作「i = 2」 ####

![1683a56a4aeb364c_w_849_h_284_f_gif_s_58413][]

比较 6 和 4 ，发生交换，**只要发生交换 i 就减 1** 。

交换前 \[ 2 6 4 1 \]『 i = 2 』

交换后 \[ 2 4 6 1 \]『 i = 1 』

#### 第六轮操作「i = 1」 ####

![1683a56a59238d49_w_849_h_284_f_gif_s_34234][]

比较 2 和 4 ，不交换，**只要不要换就自增 1** 。

交换前 \[ 2 6 4 1 \]『 i = 1 』

交换后 \[ 2 4 6 1 \]『 i = 2 』

#### 第七轮操作「i = 2」 ####

![1683a56a69973a0b_w_849_h_284_f_gif_s_37032][]

比较 4 和 6 ，不交换，**只要不要换就自增 1** 。

交换前 \[ 2 4 6 1 \]『 i = 2 』

交换后 \[ 2 4 6 1 \]『 i = 3 』

#### 第八轮操作「i = 3」 ####

![1683a56a6a5948ac_w_849_h_284_f_gif_s_58152][]

比较 6 和 1 ，发生交换，**只要发生交换 i 就减 1** 。

交换前 \[ 2 4 6 1 \]『 i = 3 』

交换后 \[ 2 4 1 6 \]『 i = 2 』

#### 第九轮操作「i = 2」 ####

![1683a56a6f54f0f3_w_849_h_284_f_gif_s_56016][]

比较 4 和 1 ，发生交换，**只要发生交换 i 就减 1** 。

交换前 \[ 2 4 1 6 \]『 i = 2 』

交换后 \[ 2 1 4 6 \]『 i = 1 』

#### 第十轮操作「i = 1」 ####

![1683a56a70ad5a94_w_849_h_284_f_gif_s_57170][]

比较 2 和 1 ，发生交换，**只要发生交换 i 就减 1** 。

交换前 \[ 2 1 4 6 \]『 i = 1 』

交换后 \[ 1 2 4 6 \]『 i = 0 』

#### 第十一轮操作「i = 0」 ####

![1683a56a7089a4da_w_849_h_284_f_gif_s_86734][]

啥也不干，先让 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 ###

鸡尾酒排序和地精排序虽然被程序员小吴归为奇葩排序一类，但是它们还是有一定的使用场景的。

*  在「大部分元素有序」的情况下，使用鸡尾酒排序可以减少排序的回合数。
 *  地精排序最著名的特点是代码只有一层循环，在「大部分元素有序」的情况下，可以减少排序回合数。

### 今日问题 ###

除了鸡尾酒排序和地精排序以外，你还知道哪些排序适合用于「大部分元素有序」的序列进行排序？

转载于:https://www.cnblogs.com/fivestudy/p/10253454.html

[1683a569b8f9419f_w_954_h_537_f_gif_s_906068]: /images/20210725/de45588217df486a9509e2f3b3108104.png
[1683a569b9213adb_w_1706_h_308_f_png_s_26112]: /images/20210725/956f33c67f0643be8bf355bca86d5ce0.png
[8 _ 1 _]: /images/20210725/3e7b0b7909a04eab932f02a8472ba1e8.png
[7 _ 1 _]: /images/20210725/d2a90eee707e436a9b1321a0f039a84a.png
[6 _ 1 _]: /images/20210725/cc18311313864e05bbe797325c3246eb.png
[5 _ 1 _]: /images/20210725/094794fba4f74cb4bb85a9971e72e268.png
[4 _ 1 _]: /images/20210725/3619001fcd4c4096af99aadaf40b8fd4.png
[3 _ 1 _]: /images/20210725/abe705881eda4371be38464a6f614ca5.png
[2 _ 1 _]: /images/20210725/355b50ef78ed4a29a11cadb2f8c9d243.png
[1683a569ef8b3ade_w_277_h_257_f_gif_s_900082]: /images/20210725/d6ad64834cda4b67a57487fd44fd3663.png
[8 _ 1 _ 1]: /images/20210725/e241ffa318444b89a920bd448f683e83.png
[_ _]: /images/20210725/a7070364f1a441bfbb54a70ee48c65fa.png
[_ _ 1]: /images/20210725/22141ba064f248fcb8a79351d0a04a3f.png
[1683a56a2dd5946a_w_849_h_284_f_gif_s_22189]: /images/20210725/58c7543f58b04ea69fcad3efb8df5ad7.png
[1683a56a2f974af7_w_849_h_284_f_gif_s_60337]: /images/20210725/610d0892c4db406b8cfb7f7412fba6c3.png
[1683a56a472e0671_w_849_h_284_f_gif_s_35838]: /images/20210725/616641250a664be9b3aa8dd0e3a2c891.png
[1683a56a45323fb0_w_849_h_284_f_gif_s_39303]: /images/20210725/af444c833fa146a989e8af0a46c173dd.png
[1683a56a4aeb364c_w_849_h_284_f_gif_s_58413]: /images/20210725/36295549cad04b598a668a7e66240954.png
[1683a56a59238d49_w_849_h_284_f_gif_s_34234]: /images/20210725/5b32fafc09b64ecfa6c4523cdb0aa4f6.png
[1683a56a69973a0b_w_849_h_284_f_gif_s_37032]: /images/20210725/a00ad1ca8a2e43b882a4e7cf9ad6f881.png
[1683a56a6a5948ac_w_849_h_284_f_gif_s_58152]: /images/20210725/449821c09c2a470f882b1fb648ff49bd.png
[1683a56a6f54f0f3_w_849_h_284_f_gif_s_56016]: /images/20210725/d0e7bb8f035644688ba6adfd7a59dc97.png
[1683a56a70ad5a94_w_849_h_284_f_gif_s_57170]: /images/20210725/6d07c984c4d2405f97bedd0700e3ad0c.png
[1683a56a7089a4da_w_849_h_284_f_gif_s_86734]: /images/20210725/e25ce64104c34f91a088e735badcf6f2.png