冒泡排序之升华版

2024-09-02 04:38

文章标签 冒泡排序升华

本文主要是介绍冒泡排序之升华版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.冒泡算法是依次比较两个相邻的位置，如果不符合规则，则交换，比较完这一趟后，在接着比较下一趟。

用程序实现是这样的

public static void main(String[] args) {int[] arr = new int[]{3,2,1,7,8,9};maoPao(arr);
}public static void maoPao(int[] arr) {boolean sorted = true;for (int i = 0; i < arr.length; i++) {	System.out.println("第"+(i+1)+"趟");for (int j = 0; j < arr.length-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr,j,j+1);	}System.out.println("第"+j+"次"+Arrays.toString(arr));}System.out.println("第"+(i+1)+"趟后"+Arrays.toString(arr));System.out.println();}
}//交换两个数的位置
public static void swap(int[] arr, int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

运行结果如下

第1趟
第0次[2, 3, 1, 7, 8, 9]
第1次[2, 1, 3, 7, 8, 9]
第2次[2, 1, 3, 7, 8, 9]
第3次[2, 1, 3, 7, 8, 9]
第4次[2, 1, 3, 7, 8, 9]
第1趟后[2, 1, 3, 7, 8, 9]

第2趟
第0次[1, 2, 3, 7, 8, 9]
第1次[1, 2, 3, 7, 8, 9]
第2次[1, 2, 3, 7, 8, 9]
第3次[1, 2, 3, 7, 8, 9]
第2趟后[1, 2, 3, 7, 8, 9]

第3趟
第0次[1, 2, 3, 7, 8, 9]
第1次[1, 2, 3, 7, 8, 9]
第2次[1, 2, 3, 7, 8, 9]
第3趟后[1, 2, 3, 7, 8, 9]

第4趟
第0次[1, 2, 3, 7, 8, 9]
第1次[1, 2, 3, 7, 8, 9]
第4趟后[1, 2, 3, 7, 8, 9]

第5趟
第0次[1, 2, 3, 7, 8, 9]
第5趟后[1, 2, 3, 7, 8, 9]

第6趟
第6趟后[1, 2, 3, 7, 8, 9]

但是这种情况又缺陷，做了好多无用功，在第二趟之后，已经实现顺序排列了，就没必要排序了，于是升华一下代码。

2.升华篇

public static void main(String[] args) {int[] arr = new int[]{3,2,1,7,8,9};maoPao(arr);
}public static void maoPao(int[] arr) {boolean sorted = true;for (int i = 0; i < arr.length; i++) {sorted = true;//假定有序System.out.println("第"+(i+1)+"趟");for (int j = 0; j < arr.length-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr,j,j+1);sorted = false;//假定失败}System.out.println("第"+j+"次"+Arrays.toString(arr));}if (sorted) {//减少趟数break;}System.out.println("第"+(i+1)+"趟后"+Arrays.toString(arr));System.out.println();}
}//交换两个数的位置
public static void swap(int[] arr, int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

运行结果如下