【小白学算法】11. 排序算法-冒泡排序，以及优化
一、冒泡排序
1.介绍
冒泡排序基本思想：
•通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值。•如果发现逆序则交换，让值较大的元素逐渐从前向后移动。•就像水底下的气泡一样逐渐向上冒。
2.理解
举例：将5个无序的数使用冒泡从小到大排序，[3, 9, -1, 10, -2]。
不着急写代码，先来根据冒泡排序的思想，手动的来排一次，记录下过程。
第一趟排序 // 每次从头开始往后比较算作一趟
3, 9, -1, 10, -2 // 第一次 3和9比较，不动（每次相邻的比较，算作一次）
3, -1, 9, 10, -2 // 第二次 9和-1比较，交换位置
3, -1, 9, 10, -2 // 第三次 9和10比较，不动
3, -1, 9, -2, 10 // 第四次 10和-2比较，交换位置
第一趟下来的结果，发现10是最大的
第二趟排序
-1, 3, 9, -2, 10 // 第一次 3和-1比较，交换位置
-1, 3, 9, -2, 10 // 第二次 3和9比较，不动
-1, 3, -2, 9, 10 // 第三次 9和-2比较，交换位置
因为10是确定了，所以9和10不用再比较了。
第二趟下来的结果，又确定了9。
第三趟排序
-1, 3, -2, 9, 10 // 第一次 -1和3比较，不动
-1, -2, 3, 9, 10 // 第二次 3和-2比较，交换位置
因为9也确定了，所以3和9不用再比较了。
第三趟下来的结果，又确定了3。
第四趟排序
-2, -1, 3, 9, 10 // 第一次 -1和-2比较，交换位置
这时候后面4个数都确定下来了，所以就不用继续比较了。
现在，从上面的比较过程，可以看出冒泡排序的规则特点：
•一共要走的趟数也就是数组循环，是 数组的大小 - 1。•在每一趟中，比较的次数在逐渐减少。•如果在某趟排序中，一次交换都没发送，那么就可以提前结束排序（优化）。
3. 代码实现
如果把上面的过程代码化，是这样的：
package sort;
import java.util.Arrays;
public class BubbleSorting {
public static void main(String[] args) {
int arr[] = {3, 9, -1, 10, -2};
int temp = 0;
// 第一趟排序
for (int j = 0; j < arr.length -1; j++) {
// 如果前面的数比后面的大，交换位置
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第一趟排序后的数组：");
System.out.println(Arrays.toString(arr));
// 第二趟排序
for (int j = 0; j < arr.length -1 - 1; j++) {
// 如果前面的数比后面的大，交换位置
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第二趟排序后的数组：");
System.out.println(Arrays.toString(arr));
// 第三趟排序
for (int j = 0; j < arr.length -1 - 2; j++) {
// 如果前面的数比后面的大，交换位置
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第三趟排序后的数组：");
System.out.println(Arrays.toString(arr));
// 第四趟排序
for (int j = 0; j < arr.length -1 - 3; j++) {
// 如果前面的数比后面的大，交换位置
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第三趟排序后的数组：");
System.out.println(Arrays.toString(arr));
}
}
运行输出：
第一趟排序后的数组：
[3, -1, 9, -2, 10]
第二趟排序后的数组：
[-1, 3, -2, 9, 10]
第三趟排序后的数组：
[-1, -2, 3, 9, 10]
第三趟排序后的数组：
[-2, -1, 3, 9, 10]
Process finished with exit code 0
运行结果与推演的一致。现在发现上面4个for循环中，一直在变的其实只是j < arr.length - 1 - ?
所以，最终的代码就出来了：
package sort;
import java.util.Arrays;
public class BubbleSorting {
public static void main(String[] args) {
int arr[] = {3, 9, -1, 10, -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));
}
}
}
二、冒泡排序优化
优化点就是如果一次交换都没发生，那么就可以提前结束排序。所以，需要在代码加个标识来标记每趟循环中是否发送了交换。
package sort;
import java.util.Arrays;
public class BubbleSorting {
public static void main(String[] args) {
int arr[] = {-1, 0, 1, 10, 20};
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;
}
}
System.out.println("第"+(i+1)+"趟排序后的数组：");
System.out.println(Arrays.toString(arr));
if (!flag) { // 在一趟排序中，一次交换都没有
break;
} else {
flag = false; // 重置flag，进行后续的判断
}
}
}
}
代码里的测试用数组我已经改成了一个有序数组了，这样的话，算法只会排一次序就不再继续了，运行：
第1趟排序后的数组：
[-1, 0, 1, 10, 20]
Process finished with exit code 0
理解算法的过程，有助于记忆。