冒泡排序（Bubble Sort）

1，正常写法

① 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
执行完一轮后，最末尾那个元素就是最大的元素
② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①，直到全部元素有序

 Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length-1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                }
            }
        }

  System.out.println(" count = " + count);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "_");
        }

 count = 28
3_4_5_5_6_7_7_8_

2，优化1

如果序列已经完全有序，可以提前终止冒泡排序

  Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length -1; end > 0; end--) {
            boolean sorted = true ;
            for (int begin = 1; begin <=end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sorted = false ;
                }
            }

            if(sorted) break;
        }

2，优化2

如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数

     Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length -1; end > 0; end--) {
            int  sortedIndex = 1 ;
            for (int begin = 1; begin <=end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sortedIndex = begin ;
                }
            }

           end = sortedIndex;
        }

3，优化方式：鸡尾酒排序，也叫双向冒泡排序，看到别人的 ，优不优，我没研究

public static Integer[] sort(Integer[] arr){
    //依次将最大的数放置到数组末尾，将第二大的数放到倒数第二位...
    boolean changed;
    for(int i = 0;i < arr.length/2;i++){
        changed = false;
        //从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
        for(int j = i;j < arr.length-1-i;j++){

            if(arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
                changed =true;
            }
        }
        if(!changed){
            break;
        }
        for(int j = arr.length-1-i; j > i; j--){

            if(arr[j]<arr[j-1]) {
                swap(arr,j,j-1);
                changed = true;
            }
        }
        if(!changed){
            break;
        }
    }
    return arr;
}

public static void swap(Integer[] arr, int pos1, int pos2){
    int temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

◼ 最坏、平均时间复杂度：O(n2)
◼ 最好时间复杂度：O(n)
◼ 空间复杂度：O(1)