鸡尾酒算法排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了鸡尾酒算法排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2083字，纯文字阅读大概需要3分钟。
内容图文
上一篇介绍了冒泡算法及其优化方案，但其优化是从每轮的比较次数上优化，而“鸡尾酒算法”可以从轮次上优化。
一、什么时鸡尾酒排序？
鸡尾酒排序又称为快乐小时排序，它基于冒泡排序进行的优化方案。
二、鸡尾酒算法思想
冒泡排序是元素单向比较，而鸡尾酒排序却是双向。
列举一个最简单的栗子array[2, 3, 4, 5, 6, 7, 8, 9, 1]，
如果按照传统的冒泡排序进行操作，
第一轮结果：[2, 3, 4, 5, 6, 7, 8, 1, 9]，只有9和1交换；
第二轮结果：[2, 3, 4, 5, 6, 7, 1, 8, 9]，只有8和1交换；
第三轮结果：[2, 3, 4, 5, 6, 1, 7, 8, 9]，只有7和1交换；
。。。
第八轮结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]，只有2和1交换；
每一轮执行过程中，前面元素的比较，很明显做了无用功，对于本次栗子中的数组，如果元素比较的顺序是从右边开始，那就省了很多功夫，加入鸡尾酒算法，可以实现这个操作。
鸡尾酒算法实现冒泡排序的优化第一版：
public
void sortArray(int[] array){
int temp=0;
boolean isSorted = true;
for(int i=0; i<array.length/2-1; i++){
isSorted = true;
//奇数轮比较for(int j=i; j<array.length-i-1; j++){
if(array[j]>array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isSorted = false;
}
}
if(isSorted){
break;
}
//偶数轮比较for(int j=array.length-i-1; j>i; j--){
if(array[j]<array[j-1]){
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
isSorted = false;
}
}
if(isSorted){
break;
}
}
}
大循环中我们将循环轮次优化为array.length/2次，奇数轮比较顺序从左到右，每一轮 j 的开始项也从冒泡算法的0变成了 i ，因为下面还有偶数轮比较排序，偶数轮排序会将最左边的元素变成有序区。
但是上一篇说到两种优化方案，这里也有基于鸡尾酒算法的两种优化方案。
鸡尾酒算法实现冒泡排序的优化第二版：
public
void sortArray(int[] array){
int temp=0;
boolean isSorted = true;
int lastRightIndex = 0;
int lastLeftIndex = 0;
//右边界int rightBorder = array.length-1;
//左边界int leftBorder = 0;
for(int i=0; i<array.length/2-1; i++){
isSorted = true;
//奇数轮比较for(int j=leftBorder; j<rightBorder; j++){
if(array[j]>array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
lastRightIndex = j;
isSorted = false;
}
}
rightBorder = lastRightIndex;
if(isSorted){
break;
}
//偶数轮比较for(int j=rightBorder; j>leftBorder; j--){
if(array[j]<array[j-1]){
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
lastLeftIndex = j;
isSorted = false;
}
}
leftBorder = lastLeftIndex;
if(isSorted){
break;
}
}
}
与传统冒泡法的第二版优化一样，设置了每一轮的循环边界，由于鸡尾酒算法是双向排序的，所以这里的边界也分别定义了左、右边界 leftBorder 和 rightBorder ，即每一轮循环都是以这两个边界为循环次数计算，相对于鸡尾酒第一版，第二版比较容易理解。
鸡尾酒算法实现冒泡排序的优化确实可以很大程度上减少了比较的无用功，同时也要注意它的代码量也是之前的两倍。
鸡尾酒算法排序介绍至此。
原文：https://www.cnblogs.com/SysoCjs/p/9403588.html
内容总结
以上是互联网集市为您收集整理的鸡尾酒算法排序全部内容，希望文章能够帮你解决鸡尾酒算法排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。