算法-冒泡排序

冒泡排序就跟 “Hello World” 一样，算是排序里第一个接触的排序算法，因其排序过程像泡泡浮动的过程而得名。

思路

核心点在于，怎么完成一趟排序的过程（假设要求按从小到大排序），

1. 从数组的第 0 位开始，和后一位进行大小比较。
2. 如果大于后者，则交换一下，这样大的值就在后面了。
3. 接着继续跟踪着这个数，再和后一位进行大小比较。
4. 直到比到数组末尾结束，这样一趟就完了。
5. 那么第二趟也是一样，从第 0 位开始，抓着它不放，依次两两比较，总共要进行 length - 1 趟。

以前学这块的时候，代码的实现有点死记硬背的感觉，现在代码实现前，我会思考些关键步骤（就像上面这样），有了关键步骤，写起来和理解起来轻松很多。

优化

上面的思路是最基础的实现，参考了书本，其实有两处可以优化改进，

1. 如果数组是部分有序的，那么对有序的部分的比较就有点浪费了。而当前趟的排序能知道下一趟排序的最终点的位置，所以可以优化每趟排序比较的终点位置，即优化步骤 4.
2. 如果数组仅调整了几个元素后就已经完成有序，那么就没必要再继续排序了。也就是说如果进行一趟排序比较发现都不用调整，那么就说明数组已经有序，此时就能省去一些趟次，即可以优化步骤 5.

对于优化点 1，可以通过记录每次交换的元素下标位置，开始下一趟排序对比时，用这个下标位置作为循环判断的终点。

对于优化点 2，可以设置标记位，排序对比开始前认为已经有序，当发生元素交换时则置为 false，表示乱序，当一趟结束，如果仍然有序就可以结束整个排序，输出结果了。

鸡尾酒排序

这个排序算法还是第一次知道，核心就是将冒泡排序中的一趟排序对比执行两遍，但是两遍的方向不同，例如第一次从位置 0 开始，那么第二次就是从位置 length - 1 开始，这么两遍算一趟。

这么来算的话，顶多需要进行 length / 2 趟。

这个算法的优势在于对于基本有序，但又是和要求的顺序是反的的情况下也能节省时间，例如要求从小到大，可偏偏数组是 {1,9,8,7,6,5,4,3,2}，这时如果两个方向进行排序对比就能很快解决。

实现完这个我在想，既然可以两遍，那是不是也能四遍一起？大概想了下应该是可行的，不过我没有测试，没有本质区别，可能最多就是省点时间，就像奶茶的中杯和大杯。

代码

github 地址：找代码里的 bubbleSort 和 cocktailSort