基本介绍
- 冒泡排序（Bubble Sorting）的基本思想是：通过对 需要排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
- 每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
- 优化一：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
- 优化二：设置结束边界，记录上一次最后交换的位置，作为下一次循环的结束边界。最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。
冒泡过程的例子（图解）
普通的冒泡排序
/**
* 冒泡法排序
* @param array 数组
*/
public static void bubbleSort(int[] array) {
// 临时变量
int temp;
// 控制比较轮次，一共 n-1 趟
for (int i = 0; i < array.length - 1; i++) {
// 上次遍历之后倒数第 i 位开始 已经是有序的了，所以这次遍历的范围是 [0,array.length - 1 - i)
for (int j = 0; j < array.length - 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
优化一：设置交换标志
冒泡法排序优化，加上flag判断是否进行了交换,没有交换就可以提前结束了。
/**
* 优化一：设置标志位
* 冒泡法排序优化,加上flag判断是否进行了交换,没有交换就可以提前结束了。
* @param array 数组
*/
public static void bubbleSortFlag(int[] array) {
// 临时变量
int temp;
// 控制比较轮次，一共 n-1 趟
for (int i = 0; i < array.length - 1; i++) {
// 标识变量，表示是否进行过交换
boolean flag = false;
// 上次遍历之后倒数第 i 位开始 已经是有序的了，所以这次遍历的范围是 [0,array.length - 1 - i)
for (int j = 0; j < array.length - 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (array[j] > array[j + 1]) {
flag = true; // 有元素交换，所以不是有序
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
// 说明在一趟排序中一次都没有进行过交换
if (!flag) {
break;
}
}
}
优化二：设置结束边界
记录上一次最后交换的位置，作为下一次循环的结束边界。最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。
/**
* 优化二：设置结束边界
* 记录上一次最后交换的位置，作为下一次循环的结束边界。
* 最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。
* @param array array
*/
public static void bubbleSort2(int[] array) {
if (array == null || array.length < 2) {
return ;
}
// 临时变量
int temp;
// 记录最后一次交换的位置
int lastExchangeIndex = 0;
// 记录里层下一次循环的终止位置
int sortBorder = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
// 标识变量，表示是否进行过交换
boolean flag = false;
for (int j = 0; j < sortBorder; j++) {
if (array[j] > array[j + 1]) {
flag = true; // 有元素交换，所以不是有序
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
// 说明在一趟排序中一次都没有进行过交换
if(!flag) {
break;
}
}
}
🤔
