JavaSE基础50题：28.（数组练习）冒泡排序

概述

给定一个整型数组，实现冒泡排序。
如：给一组数组{5，10，8，3，7}进行冒泡排序。
j一直往下走，和下一个数字进行比较，如果当前数字大于下一个数字，则两个数字交换，否则不换，继续往下走。

代码过程1

从图中我们可以看出，数组中有5个数字，比较了4趟；
且第1趟比较了4次，第2趟比较了3次，第3趟比较了2次；第四趟比较了1次。

public class P28 {
    public static void bubbleSort(int[] array) {
        //此时最外层控制的就是趟数
        for (int i = 0; i < array.length-1; i++) {
            //-i 每一趟比较的次数比上一趟比较的次数少1
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {2,10,5,3,1,4};
       bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

//运行结果
[1, 2, 3, 4, 5, 10]

代码过程2

此过程时过程1的优化。
如：给数组{5，3，7，8，10}进行排序

从图中我们可以看到，第一趟交换完之后，数据就有序了，第二趟开始就没有发生任何交换，所以我们才能说，当前数组有序了。
正常来说，不管数组有序不有序，代码1都是走array.length-1趟，所以我们优化此代码，让数组排序完成后就结束它的循环。

public class P28 {
    public static void bubbleSort(int[] array) {
        //此时最外层控制的就是趟数
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            //-i 每一次比上一次上一个比较
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {2,10,5,3,1,4};
       bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

此时运行效率大大提高。
可以用冒泡排序运行时间来比较一下，可以比较出来时间大大减少，效率大大提高！

int [] array = new int[10_0000]; //10万个数据
 for (int i = 0; i < array.length; i++) { //遍历数组,给每个数据赋值
	array[i] = i;
}
long start = System.currentTimeTimeMillis(); //冒泡排序开始的时间
bubbleSort(array);
long end = System.currentTimeTimeMillis(); //冒泡排序结束的时间
System.out.println(end - start); //冒泡排序的用时