[已解决]鸡尾酒排序怎么就比冒泡排序效率高？

超凡天赐

我怎么感觉他两的执行次数是一样的啊啊啊！！

最佳答案

月排行榜 / 总排行榜

zealstar

2017-2-4 16:58:02

我是这么理解的，具体如何算出鸡尾酒就比普通冒泡效率高我也不会

任何排序算法，大体上，遍历一遍所有元素都只能确定 1 个元素的正确位置！不管是鸡尾酒还是冒泡，都是如此。其他大多排序也只能做到这个效率。

但问题在于，在遍历元素的操作过程中，是否对目标数据外的其他数据有整理作用？
比如冒泡，规律是“大的放到后面”，那么，在遍历整个数组的过程中。除了最大的一个数据最终被放到了数组的尾部，前面的元素也经历过了交换位置的情况，有一定的整理作用。

例子： 5,4,7,3,2,8,1,9,0这个数组，经历一次冒泡后是：4,5,3,2,7,1,8,0,9
其中，9是最大的数即目标，已经成功放到最后。但是看前面的数组，8是不是比原来更接近正确位置？
那么下一次冒泡的时候，8到数组尾部需要进行交换的次数就变少了！

原理上虽然每次遍历所有元素都只是确定一个元素的正确位置，但是对于数组内其他数字的整理作用不可忽视，越往后面进行运算，其需要交换的次数就越少！

那么鸡尾酒算法比起普通冒泡，多了一种“小的放到左边”的规则，所以，整理作用就更强，每次循环过后，下次运算需要交换的次数就更少！

这个就是我的理解！

跳转到最佳答案楼层

zealstar

我是这么理解的，具体如何算出鸡尾酒就比普通冒泡效率高我也不会

任何排序算法，大体上，遍历一遍所有元素都只能确定 1 个元素的正确位置！不管是鸡尾酒还是冒泡，都是如此。其他大多排序也只能做到这个效率。

但问题在于，在遍历元素的操作过程中，是否对目标数据外的其他数据有整理作用？
比如冒泡，规律是“大的放到后面”，那么，在遍历整个数组的过程中。除了最大的一个数据最终被放到了数组的尾部，前面的元素也经历过了交换位置的情况，有一定的整理作用。

例子： 5,4,7,3,2,8,1,9,0这个数组，经历一次冒泡后是：4,5,3,2,7,1,8,0,9
其中，9是最大的数即目标，已经成功放到最后。但是看前面的数组，8是不是比原来更接近正确位置？
那么下一次冒泡的时候，8到数组尾部需要进行交换的次数就变少了！

原理上虽然每次遍历所有元素都只是确定一个元素的正确位置，但是对于数组内其他数字的整理作用不可忽视，越往后面进行运算，其需要交换的次数就越少！

那么鸡尾酒算法比起普通冒泡，多了一种“小的放到左边”的规则，所以，整理作用就更强，每次循环过后，下次运算需要交换的次数就更少！

这个就是我的理解！

fc1735

机率上的问题吧，n个数用单向的冒泡排序，很容易我就可以找到一个要跑最多次循环的，只要把最小的数放在最后一个，因为一次循环只能往左移一格，所以要跑n-1次循环。

因为单向的是只把大的往右移，小的元素还是卡在那里，结束循环的条件是，在一次循环中没移动任何元素，但是小的元素一次就移动一格..... .

双向的话，来回一次，最大最小都归位了，不只如此，去的时候会反覆移动大的元素，相对的小的元素就只被交换位置一次，回来的时候反覆移动小的元素，相对的大的就没有太大的移动，这样就达到平衡，大概是这样，要用数学严格证明鸡尾酒排序一定比冒泡排序效率高的话，那我就不会了。

超凡天赐

zealstar 发表于 2017-2-5 20:19
我是这么理解的，具体如何算出鸡尾酒就比普通冒泡效率高我也不会

任何排序算法，大体上，遍历 ...

我试了一下，有时候确实鸡尾酒排序要比冒泡排序要好一些