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 每一趟比较的次数比上一趟比较的次数少1for (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); //冒泡排序的用时