文章目录[隐藏]
鸡尾酒排序有很多称号,如双向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort), 其实就是冒泡排序的一种变形。
该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序,其实我们可以认为双向冒泡就是鸡尾酒排序,等于是冒泡排序的轻微变形。
不同的地方在于从低到高然后从高到低(有先后顺序,并非同时;大循环下第一个循环是从开始扫到结束,将最大的归到最后;
第二个循环是从倒数第二个位置往开始端扫,将最小的归到开始的位置),而冒泡排序则仅仅从低到高去比较序列里的每个元素。
他可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次只移动一个项目和。
以排序(49,38,65,97,76,13,27,14,10)为例,鸡尾酒排序只要访问一次序列就可以完成排序,但如果使用冒泡排序需要八次。但是在乱数序列的状态下,鸡尾酒排序和冒泡排序的效率都很差。
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。
他可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。
以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问两次(升序降序各一次 )次序列就可以完成排序,但如果使用冒泡排序则需要四次。
排序过程:
1、先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端
2、再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端
3、以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束
易语言鸡尾酒排序源码:
.版本 2 .子程序 鸡尾酒排序 .参数 array, 整数型, 数组 .局部变量 l, 整数型 .局部变量 r, 整数型 .局部变量 lt, 逻辑型 .局部变量 q, 整数型 .局部变量 ls, 整数型 .局部变量 m1, 整数型 l = 1 r = 取数组成员数 (array) .计次循环首 (取数组成员数 (array), ) .如果 (lt = 假) q = l ls = array [q] .变量循环首 (l + 1, r, 1, m1) .如果真 (ls > array [m1]) ls = array [m1] q = m1 .如果真结束 .变量循环尾 () swap (array [l], array [q]) ' 交换两个成员的值 l = l + 1 .否则 q = r ls = array [q] .变量循环首 (r - 1, l, -1, m1) .如果真 (ls < array [m1]) ls = array [m1] q = m1 .如果真结束 .变量循环尾 () swap (array [r], array [q]) ' 交换两个成员的值 r = r - 1 .如果结束 lt = 取反 (lt) .计次循环尾 ()
交换变量
.子程序 swap, , 公开, 用一个临时变量把 两个变量互相更换 .参数 c1, 整数型, 参考 .参数 c2, 整数型, 参考 .局部变量 m, 整数型 m = c1 c1 = c2 c2 = m