数据结构之冒泡排序

文字描述（以升序为例)

1. 依次比较数组中相邻两个元素大小，若a[i]>a[+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后
2. 重复以上步骤，直到整个数组有序

优化方式

​ 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可

基础冒泡

 @Test
    public void maopao(){
        int[] a = {1, 3, 4, 2, 10, 5, 6};
        for (int i =a.length-1; i >0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                }
            }
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

优化1：增添判断标记，发现有以此没有排序则排序完成，直接退出排序

  @Test
    public void maopao(){
        int[] a = {1, 3, 4, 2, 10, 5, 6};

        for (int i =a.length-1; i >0 ; i--) {
            boolean tag = false;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                    tag = true;
                }
            }
            System.out.print("第"+i+"次");
            for (int q = 0; q < a.length; q++) {
                System.out.print(a[q]+" ");
            }
            if (!tag) {
                break;
            }
        }
    }

优化二：

 @Test
    public void maopao(){
        int[] a = {1, 3, 4, 2, 10, 5, 6};
        int len = a.length - 1;
        while (true) {
            int last = 0;
            for (int j = 0; j < len ; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                    last = j;
                }
            }
            len = last;
            if (len == 0) {
                break;
            }
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]+" ");
            }
            System.out.println();
        }
    }



1 3 2 4 5 6 10 
1 2 3 4 5 6 10 
执行两次