简述

原理是相邻的两两元素做比较并往后移动，每轮可以选出一个最值

故最多n-1轮排完

每轮最多比较n-1-已完成轮数次

总共最多比较n*(n-1)/2次

比较并交换可以通过中间变量暂存交换值来处理

基本冒泡排序

/**
 * 冒泡排序
 * 时间复杂度On2,空间复杂度O1
 * 执行n-1轮
 * 每轮比较n-1-i次，总共比较n*(n-1)/2次
 * 最大交换n*(n-1)/2次——最坏情况：倒序
 * @author 夜神
 */
public class BubSort {

    /**
     * 向前比较 int j=arr.length-1;j>i;j--
     * @param arr
     */
    public static void forwardSort(int[] arr){
        int tmp=0;
        int count=0;
//        总共比较次数,也是最大交换次数（最坏情况：倒序）
        int compare=0;
//        n-1轮排完序,i控制轮数，隐含已经排好序的个数
        for(int i=0;i<arr.length-1;i++){
//            每轮比较n-1-i次    前序排列写法，往前面比较
            for (int j=arr.length-1;j>i;j--){
                compare++;
//             这里比较关系用的<,选取的是小值   小的向前移，拍好的在左边
                if (arr[j]<arr[j-1]){
                    tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                    count++;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("交换"+count+"次");
        System.out.println(compare+"次比较");
    }

    /**
     * 向后比较
     * 次数那里的另外一种写法 j<arr.length-1-i j从0开始，后续排列
     * @param arr
     */
    public static void backwardsSort(int[] arr){
//        交换次数
        int count=0;
//        总共比较次数,也是最大交换次数（最坏情况：倒序）
        int compare=0;
        int tmp;
//        n-1轮 i 属于[0,n-1)，即[0,n-2]
        for (int i=0;i<arr.length-1;i++){
//            每轮比较n-1-i次 总共(n-1)-0+(n-1)-1+(n-1)-2+....=(n-1)*(n-1)-(0+1+2+...+n-1-1)=(n-1)*(n-1)-(n-2)*(n-1)/2=n*(n-1)/2
            for(int j=0;j<arr.length-1-i;j++){
                compare++;
                if (arr[j]>arr[j+1]){
                    tmp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=tmp;
                    count++;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("交换"+count+"次");
        System.out.println(compare+"次比较");

    }
}