网站建设与规划试卷,做网站怎么把导航每个页面都有,开发公司绩效指标,亚马逊跨境电商开店赚钱吗7.5冒泡排序
7.5.1基本介绍
冒泡排序#xff08;Bubble Sorting#xff09;的基本思想是#xff1a;通过对待排序序列从前向后#xff08;从下标较小的元素开始#xff09;,依次比较相邻元素的值#xff0c;若发现逆序则交换#xff0c;使值较大的元素逐渐从前移向后部…7.5冒泡排序
7.5.1基本介绍
冒泡排序Bubble Sorting的基本思想是通过对待排序序列从前向后从下标较小的元素开始,依次比较相邻元素的值若发现逆序则交换使值较大的元素逐渐从前移向后部就象水底下的气泡一样逐渐向上冒。
优化 因为排序的过程中各元素不断接近自己的位置如果一趟比较下来没有进行过交换就说明序列有序因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化可以在冒泡排序写好后在进行)
7.5.2演示冒泡过程的例子(图解) 小结上面的图解过程: (1) 一共进行 数组的大小-1 次 大的循环 (2)每一趟排序的次数在逐渐的减少 (3) 如果我们发现在某趟排序中没有发生一次交换可以提前结束冒泡排序。这个就是优化
7.5.3冒泡排序应用实例
我们举一个具体的案例来说明冒泡法。我们将五个无序的数3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。
代码实现
原始的冒泡法排序
public static void main(String[] args) {int arr[] {3, 9, -1, 10, -2};//冒泡排序 的时间复杂度O(n^2)int temp 0;//临时变量for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}System.out.println(第 (i 1) 躺排序后的数组);System.out.println(Arrays.toString(arr));}}优化后的冒泡法排序 追加flag判断标识 public static void main(String[] args) {int arr[] {3, 9, -1, 10, -2};System.out.println(排序前数组);System.out.println(Arrays.toString(arr));bubbleSort(arr);System.out.println(排序后数组);System.out.println(Arrays.toString(arr));}public static void bubbleSort(int[] arr) {//冒泡排序 的时间复杂度O(n^2)int temp 0;//临时变量boolean flag false;//标识变量表示是否进行过交换for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {flag true;temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if (!flag) {break;//在一趟排序中一次交换都没有发生过} else {flag false;//重置flag进行下次判断}}}测试冒泡法排序的速度
public static void main(String[] args) {//测试一下冒泡排序的速度O(n^2), 给80000个数据 测试int arr[] new int[80000];for (int i 0, size arr.length; i size; i) {arr[i] (int) (Math.random() * 80000);//生成一个【080000)数}long startTime System.currentTimeMillis();bubbleSort(arr);long endTime System.currentTimeMillis();SimpleDateFormat dateFormat new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String start dateFormat.format(new Date(startTime));String end dateFormat.format(new Date(endTime));System.out.println(排序前时间 start);// 2023-08-20 09:57:17System.out.println(排序后时间 end);// 2023-08-20 09:57:28}public static void bubbleSort(int[] arr) {//冒泡排序 的时间复杂度O(n^2)int temp 0;//临时变量boolean flag false;//标识变量表示是否进行过交换for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {flag true;temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if (!flag) {break;//在一趟排序中一次交换都没有发生过} else {flag false;//重置flag进行下次判断}}}
