9. 冒泡排序，以及如何优化冒泡排序，冒泡排序属于插入排序

每进行一次冒泡排序，就把最大的数放在最后面这样下一次排序，就可以少进行一次比较n个数，就需要排序n-1次优化冒泡排序，如果有一次一个变量的顺序也没有改变，那么直接结束这次循环即可 package com.qin.sort; import java.lang.reflect.Array; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; //冒泡排序 public class BubbleSort { public static void main(String[] args) { int arr[] = {3,9,-1,10,20}; int arr1[] = {3,9,-1,10,20}; int arr2[] = {3,9,-1,10,20}; //为了容易理解，我们把冒泡排序的演变过程，给大家展示 //1. 第一趟排序，就是为了把最大的数排在最后面 int temp = 0 ; //临时变量 for (int i = 0; i < arr.length-1; i++) { if (arr[i]>arr[i+1]){ //前面的数比后面的数大 temp = arr[i+1]; //前面的数和后面的数进行交换 arr[i+1] = arr[i]; arr[i] = temp; } } System.out.println("第一次排序完成后的数组"); System.out.println(Arrays.toString(arr)); //第二趟排序，就是把第二大的数排在倒数第二位 for (int i = 0; i < arr.length-1-1; i++) { if (arr[i]>arr[i+1]){ //前面的数比后面的数大 temp = arr[i+1]; //前面的数和后面的数进行交换 arr[i+1] = arr[i]; arr[i] = temp; } } System.out.println("第二次排序完成后的数组"); System.out.println(Arrays.toString(arr)); //第三趟排序，就是把第三大的数排在倒数第三位 for (int i = 0; i < arr1.length-1-1-1; i++) { if (arr[i]>arr[i+1]){ //前面的数比后面的数大 temp = arr[i+1]; //前面的数和后面的数进行交换 arr[i+1] = arr[i]; arr[i] = temp; } } System.out.println("第三次排序完成后的数组"); System.out.println(Arrays.toString(arr)); //第四趟排序，就是把第四大的数排在倒数第四位 for (int i = 0; i < arr1.length-1-3; i++) { if (arr[i]>arr[i+1]){ //前面的数比后面的数大 temp = arr[i+1]; //前面的数和后面的数进行交换 arr[i+1] = arr[i]; arr[i] = temp; } } System.out.println("第四次排序完成后的数组"); System.out.println(Arrays.toString(arr)); System.out.println("============================="); //完整的冒泡排序 的时间复杂度 n^2 boolean flag = false; //标识变量，表示是否进行交换 for (int i = 0; i < arr1.length-1; i++) { for (int j = 0; j < arr1.length-1-i ; j++) { if (arr1[j]>arr1[j+1]){ //前面的数比后面的数大 flag = true; temp = arr1[j+1]; //前面的数和后面的数进行交换 arr1[j+1] = arr1[j]; arr1[j] = temp; } } System.out.printf("第%d排序后",i+1); System.out.println(Arrays.toString(arr1)); if (!flag){ //在一趟排序中，一次交换都没有发生过 break; }else { flag = false; //重置flag，方便进行下次判断 } } System.out.println("===================="); //测试封装后的方法 bubbleSort(arr2); System.out.println("排序后"); System.out.println(Arrays.toString(arr2)); System.out.println("大规模测试"); //测试一下冒泡排序的速度，给80000个数据测试 //创建要给80000个的随机的数组 int [] arr4 = new int [80000]; for (int i = 0 ; i < 80000 ; i++){ arr4[i] = (int)(Math.random() * 80000000);//生成[0,80000000)的随机数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是:"+date1Str); bubbleSort(arr4); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间是:"+date2Str); } //将冒泡排序封装为一个方法 public static void bubbleSort(int [] arr1){ int temp = 0 ; //临时变量 //完整的冒泡排序 的时间复杂度 n^2 boolean flag = false; //标识变量，表示是否进行交换 for (int i = 0; i < arr1.length-1; i++) { for (int j = 0; j < arr1.length-1-i ; j++) { if (arr1[j]>arr1[j+1]){ //前面的数比后面的数大 flag = true; temp = arr1[j+1]; //前面的数和后面的数进行交换 arr1[j+1] = arr1[j]; arr1[j] = temp; } } if (!flag){ //在一趟排序中，一次交换都没有发生过 break; }else { flag = false; //重置flag，进行下次判断 } } } } 结果