八大排序（一）：冒泡排序
开始正题，如下图，排序可以分为内部排序和外部排序。说直白一点，内部排序就是直接在内存中进行的排序，外部排序是指在数据量很大，内存无法完全加载，需要借助外部存储进行的排序。
接下来的8篇文章（包括这篇，可能不止8篇）就会介绍内部排序中的8种排序，至于外部排序，还没有深入研究过，就一笔带过了。
冒泡排序
冒泡排序可能是我们接触的最早也是最基础的排序了，我是大一上期在谭浩强老师的《C程序设计》这本书中第一次接触到的排序，也就是冒泡排序。想起当时学编程的情景，真有点掉头发呀，不过好像现在也掉头发哈。
基本思想
通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换二者，使值较大（较小）的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒，每次冒泡完就会将参与这次冒泡的元素中的最大值（最小值）排到最后。
举例：对 9、5、2、10、0 进行升序排列，排序过程如下
第1轮冒泡：第一轮冒泡针对的是所有数据，一共需要比较4次相邻元素
| 9 |
5 |
2 |
10 | 0 | |
| 9 |
5 |
9 > 5，将而二者交换 |
|||
| 5 |
9 |
2 |
10 |
0 |
|
| 9 |
2 |
9 > 2，将二者进行交换 |
|||
| 5 |
2 |
9 |
10 |
0 |
|
| 9 |
10 |
9 < 10，不交换 |
|||
| 10 |
0 |
10 > 0，将二者进行交换 |
|||
| 5 |
2 |
9 |
0 |
10 |
经过第一轮冒泡，最右边的元素已经是本次参与冒泡的元素中的最大值了，即10 |
第2轮冒泡：此次冒泡只针对前4个数，即5、2、9、0，因为经过第一次冒泡，10已经处在了正确的位置，本次冒泡一共需要比较3次相邻元素
| 5 |
2 |
9 | 0 | 10 | |
| 5 |
2 |
5 > 2，将而二者交换 |
|||
| 2 |
5 |
9 | 0 |
10 |
|
| 5 |
9 |
5 < 9，不交换 |
|||
| 9 |
0 |
9 > 0，将二者交换 | |||
| 2 |
5 |
0 | 9 |
10 |
经过第二轮冒泡，9、10都处在了正确位置 |
第3轮冒泡：由于9和10已经在正确位置，不需要在参加排序，因此参与此次冒泡的元素只有2、5、0这3个元素，本次冒泡一共需要比较2次相邻元素
| 2 |
5 |
0 |
9 | 10 | |
| 2 |
5 |
2 < 5，不交换 |
|||
| 5 |
0 |
5 > 0，交换二者位置 | |||
| 2 |
0 |
5 |
9 |
10 |
经过第3轮冒泡，5、9、10都已经排好序并处在正确位置了 |
第4轮冒泡：因为本次参与冒泡的元素只有2和0两个元素了，所以此次冒泡只需要比较一次即可，这也是最后一轮冒泡
| 2 |
0 |
5 |
9 | 10 | |
| 2 |
0 |
2 > 0，交换二者位置 |
|||
| 0 |
2 | 5 |
9 |
10 |
排序完毕 |
根据上面的排序过程，我们可以得到一个规律：如果对n个数进行排序，需要冒泡 n-1 轮，假设当前是第i（i从1开始）轮冒泡，那么这轮冒泡过程中一共要进行 n-i 次相邻元素的比较。
代码实现
public static void bubbleSort(int[] nums) {int length = nums.length;// 有 n-1 轮冒泡for (int i = 0; i < length - 1; i++) {// 每轮冒泡要比较 n-i 次相邻数据for (int j = 0; j < length - i - 1; j++) {if (nums[j] > nums[j + 1]) {int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}}}
口诀：外层循环n-1，内层循环n-i-1
优化
有时候在排序的过程中，数据可能已经是有序排列的了，不需要再继续进行比较，在这种情况就可以进行适当的优化。
比如举个极端的栗子，直接给你一个有序的数组，那还需要老老实实一轮一轮的冒泡吗，这样根本没有意义。
优化方法：用一个bool变量来标识当前轮次的冒泡中有没有进行过位置交换，如果没有的话，那说明数据已经有序了，则不需要再继续排序了。
代码如下：
public static void bubbleSort(int[] nums) {int length = nums.length;// 定义标志，标识每一轮次的冒泡有没有交换过数据boolean flag = false;// 有 n-1 轮冒泡for (int i = 0; i < length - 1; i++) {// 每轮冒泡要比较 n-i 次相邻数据for (int j = 0; j < length - i - 1; j++) {if (nums[j] > nums[j + 1]) {// 当进入这个判断后，说明这趟排序有过交换flag = true;int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}if (!flag) {// 如果flag还是false，说明这趟排序没有交换过数据// 数组已经是有序的了，那么就直接退出比较break;} else {// 如果交换过数据，重置flag为falseflag = false;}}}
时间复杂度
平均时间复杂度：O（n2）
最坏时间复杂度：O（n2）
性能测试
简单测试一下性能，代码如下：
public static void main(String[] args) {int numsCount = 100000;int[] nums = Stream.generate(() -> (int) (Math.random() * 1000000)).limit(numsCount).mapToInt(Integer::intValue).toArray();long start = System.currentTimeMillis();bubbleSort(nums);long end = System.currentTimeMillis();System.out.println("耗时：" + (end - start)+"ms");}
| numCount |
耗时 |
| 10000 |
279ms |
| 50000 |
7592ms |
| 100000 |
25934ms |
才100000数据就需要26秒，这谁等得了呀，由此可见，冒泡排序的性能不高，所以冒泡排序只适合在于数据量少的情况下使用，或者说只是为了教学使用。后面文章会介绍到其他的一些高性能排序，那速度杠杠的。
走过路过不要错过
扫码关注我