排序算法图解之Java冒泡排序及优化

目录

1.冒泡排序简介2.图解算法3.冒泡排序代码实现4.冒泡排序算法的优化

1.冒泡排序简介

冒泡排序（Bubble Sorting）即：通过对待排序的序列从前往后，依次比较相邻元素的值，若发现逆序则交换位置，使较大的元素逐渐移动到后部，就像水底的气泡一样逐渐从水面冒出来，这就是冒泡名称的由来

2.图解算法

以将序列{3, 9, -1, 10, -20}从小到大排序为例！
基本思想就是，在每一趟排序实现将最大的数移到序列的最后端！这主要通过比较相邻两个元素实现，当相邻的两个元素逆序的时候，我们就交换它们。
第1趟排序：
第1趟排序共比较了4次，将最大的数10冒泡到了序列的尾部。

第2趟排序：
由于第一趟排序已经将最大是数10给冒泡到了最末端，因此在本次排序中，不需要再比较最后一个元素，故共比较了3次，将子序列（前四个元素）中最大的数9（整个序列中倒数第二大的数）冒泡到了子序列的尾端（原序列的倒数第二个位置）。

第3趟排序：
在第三趟排序时，同理，倒数两个元素位置已经确定，即第一、第二大的数已经排好位置，只需要再将倒数第三大的数确认即可。故比较2次，实现倒数第三大的数3的位置确定。

第4趟排序：
在第四趟排序时，只有第一、第二个元素的位置还不确定，只需要比较一次，若逆序，则交换即可。到此，排序算法完成，原序列已经排序成为一个递增的序列！

小结
一共进行了数组大小-1次趟排序，即外层循环arr.length-1次；每趟排序进行了逐趟减小次数的比较，即内层循环arr.length-i-1次，i从0依次增加。

3.冒泡排序代码实现

参考代码如下，为了便于观察结果，在循环中添加了相应的输出语句：

1. import java.util.Arrays;
3. /**
4. * @author 兴趣使然黄小黄
5. * @version 1.0
6. * 冒泡排序
7. */
8. public class BubbleSort {
10.     public static void main(String[] args) {
11.         int[] array = {3, 9, -1, 10, -20};
12.         //排序前
13.         System.out.println("排序前:" + Arrays.toString(array));
15.         //冒泡排序
16.         for (int i = 0; i < array.length - 1; i++) {
17.             System.out.println("第" + (i+1) + "趟排序开始!");
18.             for (int j = 0; j < array.length - i - 1; j++) {
19.                 //如果前面的数比后面的数大，则交换
20.                 if(array[j] > array[j+1]){
21.                     //交换
22.                     int temp = array[j];
23.                     array[j] = array[j+1];
24.                     array[j+1] = temp;
25.                 }
26.                 System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
27.             }
28.             System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
29.             System.out.println("================================================");
30.         }
32.         //输出排序后的结果
33.         System.out.println("排序后:" + Arrays.toString(array));
34.     }
35. }

复制代码

实现结果：

4.冒泡排序算法的优化

举个例子，将待排序的序列改为：{5，1，2，3，4}，用以上算法来处理，观察一下结果：

可以发现，当第一趟排序结束的时候，序列已经排序完成： 即将5冒泡到了最后，序列实现了从小到大排序。但是原冒泡排序算法，还是义无反顾的进行了数组大小-1趟排序（我可真是大冤种！）
因此，我们需要尝试对算法进行优化！
发现：在冒泡排序的过程中，各个元素都在不断的接近自己的位置，如果下一趟比较中没有进行过任何交换，则说明序列已经有序， 则排序算法已经可以返回结果。因此，考虑在排序算法过程中添加一个标志flag判断元素是否进行过交换，以减少不必要的冤种行为！
优化代码如下：

1. import java.util.Arrays;
3. /**
4. * @author 兴趣使然黄小黄
5. * @version 1.0
6. * 冒泡排序优化
7. */
8. public class BubbleSort {
10.     public static void main(String[] args) {
11.         int[] array = {5, 1, 2, 3, 4};
12.         //排序前
13.         System.out.println("排序前:" + Arrays.toString(array));
15.         boolean flag = false; //用于标记是否进行了交换，true则说明进行了交换，false表示无
17.         //冒泡排序
18.         for (int i = 0; i < array.length - 1; i++) {
19.             System.out.println("第" + (i+1) + "趟排序开始!");
20.             for (int j = 0; j < array.length - i - 1; j++) {
21.                 //如果前面的数比后面的数大，则交换
22.                 if(array[j] > array[j+1]){
23.                     //交换
24.                     flag = true; //标记进行了交换
25.                     int temp = array[j];
26.                     array[j] = array[j+1];
27.                     array[j+1] = temp;
28.                 }
29.                 System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
30.             }
31.             System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
32.             System.out.println("================================================");
33.             if (!flag){
34.                 //如果没有进行交换则直接退出，说明排序已经完成
35.                 break;
36.             }else {
37.                 //回退
38.                 flag = false;
39.             }
40.         }
42.         //输出排序后的结果
43.         System.out.println("排序后:" + Arrays.toString(array));
44.     }
45. }

复制代码

四趟排序，优化成了只需要两趟排序！又是一个不可多得的小技巧！在算法程序题中，flag的设置是一种常用的编程思想，常常用于回溯算法中，小伙伴们要学会举一反三~

到此这篇关于排序算法图解之Java冒泡排序及优化的文章就介绍到这了,更多相关Java冒泡排序内容请搜索中国红客联盟以前的文章或继续浏览下面的相关文章希望大家以后多多支持中国红客联盟！