冒泡排序

冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

一般情况下，可以通过下面的动画理解冒泡排序。

现在我们来看一组特殊数据如果使用冒泡排序会怎么样。

将无序数列：2，3，4，5，6，7，8，1，使用冒泡排序使其从小到大排序。

进行逐步分析：

第一轮操作（ 8 和 1 交换）
在这里插入图片描述
第二轮操作（ 7 和 1 交换）

第三轮操作（ 6 和 1 交换）

第四轮操作（ 5 和 1 交换）

第五轮操作（ 4 和 1 交换）

第六轮操作（ 3 和 1 交换）

第七轮操作（ 2 和 1 交换）

仔细观察上面的这组无序数列，实际上只有 1 的位置不在该在的位置，而 2 ，3 ，4 ，5 ，6 ，7 ，8 都已经有序了，结果使用冒泡排序，需要折腾 7 次才能将 1 归位。

兔子示例图等待补充：

{6, 1, 2, 3, 4, 5}

从上面可以看出，冒泡排序有意i给很大的问题：它的运行时间依赖于数组的初始排序。大的数(兔子)上升得很快，而小的数(乌龟)下降的很慢。

冒泡排序中，尾部小数值称为乌龟，头部大数值叫做兔子。

鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。

在这里插入图片描述
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

排序过程：

先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端
再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端
以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束

第一轮操作（ 8 和 1 交换）
在这里插入图片描述
第二轮操作 ( 从序列右边开始遍历）

第三轮操作 ( 从左向右比较和交换 )

在这一轮操作中，没有元素位置交换，证明已经有序，排序结束。对比冒泡排序，鸡尾酒排序只需要 3 轮操作就可以完成排序。

代码实现

java

    private static void BubbleSort(int[] arr){int left = 0, right = arr.length - 1;  // 无序区间索引while (left < right){for (int i = left; i < right; i++){ //第一次比较时： i = 数组的最后一个元素的索引时跳出循环。 因为最后一个元素就不需要比较if (arr[i] > arr[i+1]){swap(arr, i, i+1);}}right--;}}private static void CocktailSort(int[] arr){int left = 0, right = arr.length - 1;  // 无序区间索引while (left < right){// 从左到右边：最大的放在右边for (int i = left; i < right; i++){if (arr[i] > arr[i+1]){swap(arr, i, i+1);}}right--;//    System.out.println(Arrays.toString(arr));// 从右到左：最小的放到右边for (int i = right; i > left; i--){if (arr[i] < arr[i-1]){swap(arr, i, i-1);}}//   System.out.println(Arrays.toString(arr));left++;}}private static void swap(int[] arr, int i , int j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = new int[]{77, 66, 33, 3,2,3,2,5,333,45566,2345678,78,990,12,432,56};CocktailSort(arr);System.out.println(Arrays.toString(arr));}

优化：一旦没有任何元素发生交换，就表示数据已经有序了

    private static void BubbleSort(int[] arr){int left = 0, right = arr.length - 1;  // 无序区间索引boolean swap = false;while (left < right){swap = false;for (int i = left; i < right; i++){ //第一次比较时： i = 数组的最后一个元素的索引时跳出循环。 因为最后一个元素就不需要比较if (arr[i] > arr[i+1]){swap(arr, i, i+1);swap = true;}}//当前这一轮比较中没有发生交换：表示有序if (swap == false){break;}right--;}}private static void CocktailSort(int[] arr){int left = 0, right = arr.length - 1;  // 无序区间索引boolean swap = false;while (left < right){swap = false;// 从左到右边：最大的放在右边for (int i = left; i < right; i++){if (arr[i] > arr[i+1]){swap(arr, i, i+1);swap = true;}}right--;//    System.out.println(Arrays.toString(arr));// 从右到左：最小的放到右边for (int i = right; i > left; i--){if (arr[i] < arr[i-1]){swap(arr, i, i-1);swap = true;}}//   System.out.println(Arrays.toString(arr));if (swap == false){break;}left++;}}private static void swap(int[] arr, int i , int j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static int[] generateRandomArray(int length, int rangeL, int rangeR){if (length <0  || rangeR <= rangeL) {return null;};return  new Random().ints(rangeL, rangeR).limit(length).toArray();}public static void main(String[] args) {//  int[] arr = new int[]{77, 66, 33, 3,2,3,2,5,333,45566,2345678,78,990,12,432,56};int [] arr =  generateRandomArray(1000000, -10000, 10000);long start = System.currentTimeMillis(); // 记录起始时间CocktailSort(arr);long end = System.currentTimeMillis();       // 记录结束时间System.out.println(end-start);System.out.println(Arrays.toString(arr));}

golang

package mainimport ("fmt"
)func bobbleSort(arr [] int)[]int{length := len(arr)if length <= 1 {return arr}else{for i := 0; i < length ; i++ {exchange := falseleft,  right :=  0,  length - 1 - i;// 无序区间索引for j := left; j < right ; j++{if arr[j] > arr[j + 1] {arr[j], arr[j + 1] = arr[j + 1], arr[j];exchange = true}}if !exchange {break}}return arr;}
}func cocktailSort(arr [] int)[]int{length := len(arr)if length <= 1 {return arr}else{left,  right :=  0,  length - 1;// 无序区间索引for left < right {exchange := falsefor j := left; j < right ; j++{if arr[j] > arr[j + 1] {arr[j], arr[j + 1] = arr[j + 1], arr[j]exchange = true}}right--for j := right; j > left ; j--{if arr[j] < arr[j - 1] {arr[j], arr[j - 1] = arr[j - 1], arr[j]exchange = true}}left++if !exchange {break}}return arr;}
}func main() {arr:=[]int {1,9,2,8,3,7,4,6,5,10, -1}fmt.Println(cocktailSort(arr))fmt.Println(arr)
}