冒泡排序

概念介绍

　　有同学想了解冒泡排序，今天它来了！冒泡排序的核心思想是：每次比较两个相邻的元素，让较大的元素升到顶端！

　　举个栗子：咱们要对[2，7，-5，30，9]这五个数进行冒泡排序，看一下流程。

　　初始序列：[2，7，-5，30，9]。

　　第一轮：我们的目标是找到最大的数，让其冒头到顶端，排在最后一位。

　　　　　　第一次：[2，7，-5，30，9]，比较2与7,7比2大，大的数已经在上边，所以不做操作。

　　　　　　第二次：[2，7，-5，30，9]，比较7与-5,7比-5大，大的数在下边，所以将7与-5调换位置，调换位置后的序列为[2，-5，7，30，9]。

　　　　　　第三次：[2，-5，7，30，9]，比较7与30,30比7大，大的数已经在上边，所以不做操作。

　　　　　　第四次：[2，-5，7，30，9]，比较30与9,30比9大，大的数在下边，所以将30与9调换位置，调换位置后的序列为[2，-5，7，9，30]。

　　第一轮结束后，我们已经让最大的数冒出头，也就是30在最顶端了。

　　第二轮：我们的目标是找出除了第一轮的最大数30外的最大值，让它排在倒数第二位。

　　　　　　第一次：[2，-5，7，9，30]，比较2与-5,2比-5大，大的数在下边，所以将2与-5调换位置，调换位置后的序列为[-5，2，7，9，30]。

　　　　　　第二次：[-5，2，7，9，30]，比较2与7,7比2大，大的数已经在上边，所以不做操作。

　　　　　　第三次：[-5，2，7，9，30]，比较7与9,9比7大，大的数已经在上边，所以不做操作。

　　第二轮结束后，我们已经让除了30以外最大的数冒出头，也就是9排在倒数第二位。

　　第三轮：我们的目标是找出除了第二轮的最大数9外的最大值，让它排在倒数第三位。

　　　　　　第一次：[-5，2，7，9，30]，比较-5与2,2比-5大，大的数已经在上边，所以不做操作。

　　　　　　第二次：[-5，2，7，9，30]，比较2与7,7比2大，大的数已经在上边，所以不做操作。

　　第三轮结束后，我们已经让除了9以外最大的数冒出头，也就是7排在倒数第三位。

　　第四轮：我们的目标是找出除了第三轮的最大数7外的最大值，让它排在倒数第四位。

　　　　　　第一次：[-5，2，7，9，30]，比较-5与2,2比-5大，大的数已经在上边，所以不做操作。

　　第四轮结束后，我们已经让除了7以外最大的数冒出头，也就是2排在倒数第四位，排序完毕。

代码实现

　　既然大家已经明白了排序的原理，那么代码实现起来还是很简单的。

 1     public static void bubbleSort(int[] arr) {
 2         // 用于帮助我们进行数据交换
 3         int temp;
 4         for (int i = 0; i < arr.length - 1; i++) {
 5             for (int j = 0; j < arr.length - 1 - i; j++) {
 6                 // 如果前面的数比后面的数大，则交换
 7                 if (arr[j] > arr[j + 1]) {
 8                     temp = arr[j];
 9                     arr[j] = arr[j + 1];
10                     arr[j + 1] = temp;
11                 }
12             }
13         }
14     }

　　前面我们举了一个例子，对[2，7，-5，30，9]进行排序，如果大家注意观察，就会发现在第二轮排序结束后，其实所有的数已经排好了，后面的操作有些浪费时间。因此，我们对冒泡排序进行优化，如果对于已经排好序的序列，我们可以提前终止程序。下面就是冒泡排序的优化版：

 1     public static void bubbleSortIncrease(int[] arr) {
 2         int temp;
 3         // 标识变量，表示是否进行过交换，如果数组是已经是有序的，则不会发生交换，可以提前终止排序行为
 4         boolean flag = false;
 5         for (int i = 0; i < arr.length - 1; i++) {
 6             for (int j = 0; j < arr.length - 1 - i; j++) {
 7                 if (arr[j] > arr[j + 1]) {
 8                     temp = arr[j];
 9                     arr[j] = arr[j + 1];
10                     arr[j + 1] = temp;
11                     // 发生过交换，修改flag为true
12                     flag = true;
13                 }
14             }
15             if (!flag) {
16                 // 如果已经排好序，则终止排序操作
17                 break;
18             } else {
19                 // 重置flag为false,
20                 flag = false;
21             }
22         }
23     }

　　至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于algorithm工程下的sort目录BubbleSort，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为你揭秘更多排序算法！