一个做音乐的网站,网站维护运营主要是做什么的,软件定制开发企云云,做网站需要什么服务器转载自 漫画#xff1a;什么是鸡尾酒排序
那么#xff0c;鸡尾酒排序又是何方神圣呢#xff1f;我们这一期将会详细讲述。 让我们首先来回顾一下冒泡排序的思想#xff1a;
冒泡排序的每一个元素都可以像小气泡一样#xff0c;根据自身大小#xff0c;一点一点向着数…转载自 漫画什么是鸡尾酒排序
那么鸡尾酒排序又是何方神圣呢我们这一期将会详细讲述。 让我们首先来回顾一下冒泡排序的思想
冒泡排序的每一个元素都可以像小气泡一样根据自身大小一点一点向着数组的一侧移动。算法的每一轮从都是从左到右比较元素进行单向的位置交换。
那么鸡尾酒排序做了怎样的优化呢
鸡尾酒排序的元素比较和交换过程是双向的。
让我们来举一个栗子 有8个数组成一个无序数列23456781希望从小到大排序。
如果按照冒泡排序的思想排序的过程是什么样呢
第一轮结果8和1交换 第二轮结果7和1交换 第三轮结果6和1交换 第四轮结果5和1交换 第五轮结果4和1交换 第六轮结果3和1交换 第七轮结果2和1交换 鸡尾酒排序是什么样子呢让我们来看一看详细过程
第一轮和冒泡排序一样8和1交换 第二轮
此时开始不一样了我们反过来从右往左比较和交换
8已经处于有序区我们忽略掉8让1和7比较。元素1小于7所以1和7交换位置 接下来1和6比较元素1小于6所以1和6交换位置
接下来1和5比较元素1小于5所以1和5交换位置
接下来1和4交换1和3交换1和2交换最终成为了下面的结果
第三轮虽然已经有序但是流程并没有结束
鸡尾酒排序的第三轮需要重新从左向右比较和交换
1和2比较位置不变2和3比较位置不变3和4比较位置不变......6和7比较位置不变。
没有元素位置交换证明已经有序排序结束。
这就是鸡尾酒排序的思路。排序过程就像钟摆一样第一轮从左到右第二轮从右到左第三轮再从左到右......
public class CockTailSort {private static void sort(int array[]){int tmp 0;for(int i0; iarray.length/2; i) {//有序标记每一轮的初始是trueboolean isSorted true;//奇数轮从左向右比较和交换for(int ji; jarray.length-i-1; j){if(array[j] array[j1]){tmp array[j];array[j] array[j1];array[j1] tmp;//有元素交换所以不是有序标记变为falseisSorted false;}}if(isSorted){break;}//偶数轮之前重新标记为trueisSorted true;//偶数轮从右向左比较和交换for(int jarray.length-i-1; ji; j--) {if(array[j] array[j-1]){tmp array[j];array[j] array[j-1];array[j-1] tmp;//有元素交换所以不是有序标记变为falseisSorted false;}}if(isSorted){break;}}
}public static void main(String[] args){int[] array new int[]{2,3,4,5,6,7,8,1};sort(array);System.out.println(Arrays.toString(array));
}
}
这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合大循环内包含两个小循环第一个循环从左向右比较并交换元素第二个循环从右向左比较并交换元素。
让我们来回顾一下冒牌排序针对有序区的优化思路 原始的冒泡排序有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1第二轮排序过后的有序区长度是2 ......
要想优化我们可以在每一轮排序的最后记录下最后一次元素交换的位置那个位置也就是无序数列的边界再往后就是有序区了。
对于单向的冒泡排序我们需要设置一个边界值对于双向的鸡尾酒排序我们需要设置两个边界值。请看代码
public class CockTailSort {private static void sort(int array[]){int tmp 0;//记录右侧最后一次交换的位置int lastRightExchangeIndex 0;//记录左侧最后一次交换的位置int lastLeftExchangeIndex 0;//无序数列的右边界每次比较只需要比到这里为止int rightSortBorder array.length - 1;//无序数列的左边界每次比较只需要比到这里为止int leftSortBorder 0;for(int i0; iarray.length/2; i){//有序标记每一轮的初始是trueboolean isSorted true;//奇数轮从左向右比较和交换for(int jleftSortBorder; jrightSortBorder; j){if(array[j] array[j1]){tmp array[j];array[j] array[j1];array[j1] tmp;//有元素交换所以不是有序标记变为falseisSorted false;lastRightExchangeIndex j;}}rightSortBorder lastRightExchangeIndex;if(isSorted){break;}//偶数轮之前重新标记为trueisSorted true;//偶数轮从右向左比较和交换for(int jrightSortBorder; jleftSortBorder; j--){if(array[j] array[j-1]){tmp array[j];array[j] array[j-1];array[j-1] tmp;//有元素交换所以不是有序标记变为falseisSorted false;lastLeftExchangeIndex j;}}leftSortBorder lastLeftExchangeIndex;if(isSorted){break;}}
}public static void main(String[] args){int[] array new int[]{2,3,4,5,6,7,8,1};sort(array);System.out.println(Arrays.toString(array));
}
}
代码中使用了左右两个边界值rightSortBorder 代表右边界leftSortBorder代表左边界。
在比较和交换元素时奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
