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

梦里梦外; 2022-02-01 07:25 198阅读 0赞

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

从冒泡排序开始，先来看回顾一下冒泡排序的思想和原理。  
**冒泡排序的思想**  
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。  
**冒泡排序算法的原理**

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。  
    ![冒泡排序][20190513195748136.gif]  
    现在我们来看一组特殊数据如果使用冒泡排序会怎么样。  
    将无序数列：2，3，4，5，6，7，8，1，使用冒泡排序使其从小到大排序。  
    ![在这里插入图片描述][20190513195808432.png]  
    无序数列  
    进行逐步分析：  
    第一轮操作（ 8 和 1 交换 ）  
    ![在这里插入图片描述][20190513195819740.gif]  
    第二轮操作（ 7 和 1 交换 ）  
    ![在这里插入图片描述][20190513195842834.gif]  
    第三轮操作（ 6 和 1 交换 ）  
    ![在这里插入图片描述][20190513195948881.gif]  
    第四轮操作（ 5 和 1 交换 ）  
    ![在这里插入图片描述][20190513195958921.gif]  
    第五轮操作（ 4 和 1 交换 ）  
    ![在这里插入图片描述][20190513200006519.gif]  
    第六轮操作（ 3 和 1 交换 ）  
    ![在这里插入图片描述][20190513200016934.gif]  
    第七轮操作（ 2 和 1 交换 ）  
    ![在这里插入图片描述][20190513200028666.gif]  
    仔细观察上面的这组无序数列，实际上只有 1 的位置不在该在的位置，而 2 ，3 ，4 ，5 ，6 ，7 ，8 都已经有序了，结果使用冒泡排序，需要 折腾 7 次 才能将 1 归位。  
    鸡尾酒排序  
    ![在这里插入图片描述][20190513200043121.gif]  
    **鸡尾酒排序**，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。  
    **排序过程：**  
    先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端  
    再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端  
    以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束

第一轮操作（ 8 和 1 交换 ）  
![在这里插入图片描述][20190513200140938.gif]  
第二轮操作 ( 从序列右边开始遍历 ）  
![在这里插入图片描述][20190513200152161.gif]  
第三轮操作 ( 从左向右比较和交换 )  
![在这里插入图片描述][20190513200201305.gif]  
在这一轮操作中，没有元素位置交换，证明已经有序，排序结束。对比冒泡排序 ，鸡尾酒排序只需要 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」  
![在这里插入图片描述][2019051320025433.gif]  
先让 i 自增 1 ，达到值为 1 才开始比较 ：  
交换前 \[ 6 2 4 1 \] 『 i = 0 』  
交换后 \[ 6 2 4 1 \] 『 i = 1 』

第二轮操作「i = 1」  
![在这里插入图片描述][20190513200324972.gif]  
比较 6 和 2 ，发生交换，只要发生交换 i 就减 1 。  
交换前 \[ 6 2 4 1 \]『 i = 1 』  
交换后 \[ 2 6 4 1 \]『 i = 0 』

第三轮操作「i = 0」  
![在这里插入图片描述][20190513200404106.gif]  
i 变成 0 了，啥也不干，自增变成 1 再说。  
交换前 \[ 2 6 4 1 \]『 i = 0 』  
交换后 \[ 2 6 4 1 \]『 i = 1 』

第四轮操作「i = 1」  
![在这里插入图片描述][20190513200421878.gif]  
比较 2 和 6 ，不交换，只要不要换就自增 1。  
交换前 \[ 2 6 4 1 \]『 i = 1 』  
交换后 \[ 2 6 4 1 \]『 i = 2 』

第五轮操作「i = 2」  
![在这里插入图片描述][20190513200438189.gif]  
比较 6 和 4 ，发生交换，只要发生交换 i 就减 1 。  
交换前 \[ 2 6 4 1 \]『 i = 2 』  
交换后 \[ 2 4 6 1 \]『 i = 1 』

第六轮操作「i = 1」  
![在这里插入图片描述][20190513200452661.gif]  
比较 2 和 4 ，不交换，只要不要换就自增 1 。  
交换前 \[ 2 6 4 1 \]『 i = 1 』  
交换后 \[ 2 4 6 1 \]『 i = 2 』

第七轮操作「i = 2」  
![在这里插入图片描述][20190513200504212.gif]  
比较 4 和 6 ，不交换，只要不要换就自增 1 。  
交换前 \[ 2 4 6 1 \]『 i = 2 』  
交换后 \[ 2 4 6 1 \]『 i = 3 』

第八轮操作「i = 3」  
![在这里插入图片描述][20190513200543783.gif]  
比较 6 和 1 ，发生交换，只要发生交换 i 就减 1 。  
交换前 \[ 2 4 6 1 \]『 i = 3 』  
交换后 \[ 2 4 1 6 \]『 i = 2 』

第九轮操作「i = 2」  
![在这里插入图片描述][20190513200557345.gif]  
比较 4 和 1 ，发生交换，只要发生交换 i 就减 1 。  
交换前 \[ 2 4 1 6 \]『 i = 2 』  
交换后 \[ 2 1 4 6 \]『 i = 1 』

第十轮操作「i = 1」  
![在这里插入图片描述][20190513200609172.gif]  
比较 2 和 1 ，发生交换，只要发生交换 i 就减 1 。  
交换前 \[ 2 1 4 6 \]『 i = 1 』  
交换后 \[ 1 2 4 6 \]『 i = 0 』

第十一轮操作「i = 0」  
![在这里插入图片描述][20190513200619799.gif]  
啥也不干，先让 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 \]。  
地精排序算法代码

template <class T>
    void gnome_sort_1(T data[], int n, bool comparator(T, T)){
    	int i = 1;
        while (i < n){
        	if (i > 0 && comparator(data[i], data[i-1])){
        		swap(data[i], data[i-1]);
            	i--;
        	}else{
            	i++;
        	}
    	}
    }

这种地精排序算法还有很多优化的空间，这里就不展开来讲了。

[20190513195748136.gif]: /images/20220201/730ba581cb144efb84d96acd8c385872.png
[20190513195808432.png]: /images/20220201/d85d8e9c2c974e7eb9d9dbea24e25799.png
[20190513195819740.gif]: /images/20220201/bfd16ce7fac746f1a1fa923085ffb8fc.png
[20190513195842834.gif]: /images/20220201/5ef6c5eb4a27414c8129609a3d3a89af.png
[20190513195948881.gif]: /images/20220201/d93770257a4d4014ab35503644540b39.png
[20190513195958921.gif]: /images/20220201/a94a2017d62c48c9aedd760b1715e07e.png
[20190513200006519.gif]: /images/20220201/31cfa893adc04b96b81dec026a5e0aef.png
[20190513200016934.gif]: /images/20220201/d45347a02f3c44a7b405a6249955fc8e.png
[20190513200028666.gif]: /images/20220201/d6962ea40322458ba650b91b8d6ad624.png
[20190513200043121.gif]: /images/20220201/60341b91e60343b898c837abff8cf2f4.png
[20190513200140938.gif]: /images/20220201/80436e1d277347ee98c25aeba32f8c24.png
[20190513200152161.gif]: /images/20220201/f2fac365451544c79dc39af3d785d18a.png
[20190513200201305.gif]: /images/20220201/165870058fe54546b7b300de767fa3b3.png
[2019051320025433.gif]: /images/20220201/7c02040132de4493bd89ed3447a9ce54.png
[20190513200324972.gif]: /images/20220201/16b1f6ab3f9445179949c6bd7744f585.png
[20190513200404106.gif]: /images/20220201/2134b62e482140f5bdee2a1f7680fe17.png
[20190513200421878.gif]: /images/20220201/3fafd0cb39d3417885acc5bc593ae353.png
[20190513200438189.gif]: /images/20220201/b1b279c417704e01ba6c966db4304201.png
[20190513200452661.gif]: /images/20220201/c2a853355e424511b34ed4362293ccaa.png
[20190513200504212.gif]: /images/20220201/054f8158770c4c4bb3bdfa8a65135529.png
[20190513200543783.gif]: /images/20220201/7d9c6ee1b2c9405d9892219ca2ca56d3.png
[20190513200557345.gif]: /images/20220201/923b3dd60d944964b7100a2126966426.png
[20190513200609172.gif]: /images/20220201/78b3cb4e6a29432e8909b7ab0f8ecf18.png
[20190513200619799.gif]: /images/20220201/487f08e80a6d479c9453f32567d9d727.png