鸡尾酒排序怎么就比冒泡排序效率高？
本帖最后由 超凡天赐 于 2017-2-5 23:38 编辑我怎么感觉他两的执行次数是一样的啊啊啊！！ 我是这么理解的，具体如何算出鸡尾酒就比普通冒泡效率高我也不会{:10_266:}
任何排序算法，大体上，遍历一遍所有元素都只能确定 1 个元素的正确位置！不管是鸡尾酒还是冒泡，都是如此。其他大多排序也只能做到这个效率。
但问题在于，在遍历元素的操作过程中，是否对目标数据外的其他数据有整理作用？
比如冒泡，规律是“大的放到后面”，那么，在遍历整个数组的过程中。除了最大的一个数据最终被放到了数组的尾部，前面的元素也经历过了交换位置的情况，有一定的整理作用。
例子： 5,4,7,3,2,8,1,9,0这个数组，经历一次冒泡后是：4,5,3,2,7,1,8,0,9
其中，9是最大的数即目标，已经成功放到最后。但是看前面的数组，8是不是比原来更接近正确位置？
那么下一次冒泡的时候，8到数组尾部需要进行交换的次数就变少了！
原理上虽然每次遍历所有元素都只是确定一个元素的正确位置，但是对于数组内其他数字的整理作用不可忽视，越往后面进行运算，其需要交换的次数就越少！
那么鸡尾酒算法比起普通冒泡，多了一种“小的放到左边”的规则，所以，整理作用就更强，每次循环过后，下次运算需要交换的次数就更少！
这个就是我的理解！{:10_245:}
机率上的问题吧，n个数用单向的冒泡排序，很容易我就可以找到一个要跑最多次循环的，只要把最小的数放在最后一个，因为一次循环只能往左移一格，所以要跑n-1次循环。
因为单向的是只把大的往右移，小的元素还是卡在那里，结束循环的条件是，在一次循环中没移动任何元素，但是小的元素一次就移动一格..... .
双向的话，来回一次，最大最小都归位了，不只如此，去的时候会反覆移动大的元素，相对的小的元素就只被交换位置一次，回来的时候反覆移动小的元素，相对的大的就没有太大的移动，这样就达到平衡，大概是这样，要用数学严格证明鸡尾酒排序一定比冒泡排序效率高的话，那我就不会了。 zealstar 发表于 2017-2-5 20:19
我是这么理解的，具体如何算出鸡尾酒就比普通冒泡效率高我也不会
任何排序算法，大体上，遍历 ...
我试了一下，有时候确实鸡尾酒排序要比冒泡排序要好一些{:10_256:}
页:
[1]