排序算法之鸡尾酒排序
【排序算法之鸡尾酒排序】5.3 鸡尾酒排序（Cocktail sort）
既然介绍了冒泡排序。就不得不说一下冒泡排序最为重要的一个变种——鸡尾酒排序（也称为定向冒泡排序）。此算法与冒泡排序的不同之处在于鸡尾酒排序是双向进行的，而冒泡排序则是单向进行的。
关于两种排序的效率方面，鸡尾酒排序在某些情况下比冒泡排序略微好那么一点点。
只是，在大部分乱序的情况下，鸡尾酒排序与冒泡排序的效率都非常差劲。
以数组{2,8,7,1,3}为例。鸡尾酒排序过程如图5-3所看到的。
文章图片
其排序过程，也可參照例如以下动态图。
文章图片
该动态图的原始链接为：http://zh.wikipedia.org/wiki/File:Sorting_shaker_sort_anim.gif
C代码实现：
#include
#include
#include void exchange(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
//鸡尾酒排序
void cocktail_sort(int a[], int length) {
for(int i=0;
i=0;
j++) {
index = length-j-2;
if( a[index]>a[index+1] ) {
exchange(a[index], a[index+1]);
}
}
i++;
//将较大的数换到数组末尾
for(int j=(i+1)/2;
ja[index+1] ) {
exchange(a[index], a[index+1]);
}
}
i++;
}
}int main(int argc, char** argv) {
const int length = 10;
int a[length];
//告诉rand方法，以time为种子去生成随机数
srand( (unsigned)time(NULL) );
for(int i=0;
i C++代码实现为：
#include
#include
#include
#include
using namespace std;
void exchange(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void cocktail_sort(vector &a) {
vector::iterator itStart = a.begin();
vector::iterator itEnd = a.end();
for(size_t i=0;
i::iterator jt=itEnd-2-i/2;
jt>=i/2+itStart;
jt-- ) {
if( *(jt)>*(jt+1) ) {
exchange(*(jt), *(jt+1));
}
//防止操作到vector以外的空间
if( jt==itStart ){
break;
}
}
i++;
//将较大的数换到数组末尾
for(vector::iterator jt=(i+1)/2+itStart;
jt*(jt+1) ) {
exchange(*(jt), *(jt+1));
}
//防止操作到vector以外的空间
if( jt==itEnd-2 ){
break;
}
}
i++;
}
}
void show(vector &a){
for(vector::iterator it=a.begin();
it(time(NULL)) );
for(int i=0;
i aVec(a, a+length);
show(aVec);
cocktail_sort(aVec);
show(aVec);
return 0;
} 推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 太平之莲
- 闲杂“细雨”
- 七年之痒之后
- 深入理解Go之generate
- 由浅入深理解AOP
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 生活随笔｜好天气下的意外之喜
- 感恩之旅第75天
- python学习之|python学习之 实现QQ自动发送消息