常用12大排序算法之十二:鸡尾酒(双向冒泡或改进冒泡)排序算法

2017-04-23 00:46 阅读 5,043 次 评论 0 条

1.鸡尾酒(双向冒泡)排序简介

鸡尾酒排序也就是“定向冒泡排序”、“双向冒泡排序”和“改进冒泡排序”, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

 

2.鸡尾酒(双向冒泡)排序基本原理

使用鸡尾酒排序为一列数字进行排序的过程可以通过右图形象的展示出来:
数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。

算法原理:数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。

 

3.鸡尾酒(双向冒泡)排序算法基本过程

(1)先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端;

(2)再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端;

以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束.

 

4.鸡尾酒(双向冒泡)排序算法分析

(1)时间复杂度:鸡尾酒排序的效率还是很低的,两层循环,时间复杂度为 O(n^2) 。

(2)空间复杂度:由于只需要几个临时变量,所以空间复杂度为 O(1) 。

那么何以见得鸡尾酒排序比冒泡排序好一点呢?

考虑这样的一个序列:(2,3,4,5,1) 。如果使用鸡尾酒排序,一个来回就可以搞定;而冒泡排序则需要跑四趟。

根本原因在于冒泡是单向的,如果从左向右冒泡,对于小数靠后就会很不利(一趟只能挪一个位置,那就需要多次循环。这种数又被称之为乌龟);相应的,如果从右向左冒泡,对于大数靠前又会很不利(靠前的一只大乌龟)。鸡尾酒排序的优点就在于这里,由于在序列中左右摇摆(为此鸡尾酒排序又称之为 shaker sort),两种较差的局面就能得到规避,以此在性能上带来一些提升。

 

5.鸡尾酒(双向冒泡)排序算法C语言源代码

 

6.鸡尾酒(双向冒泡)排序算法C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之十二:鸡尾酒(双向冒泡或改进冒泡)排序算法 | 算法君

发表评论


表情