冒泡算法的规则：
每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放待排序序列的起始位置(或末尾位置），直到全部待排序的数据元素排完
动态图：
对应代码
static void swap(int[] arr, int addr1, int addr2) { //数组数据交换
if (addr1 == addr2) {
return;
}
arr[addr1] = arr[addr1] ^ arr[addr2];
arr[addr2] = arr[addr1] ^ arr[addr2];
arr[addr1] = arr[addr1] ^ arr[addr2];
}
static void bubbleSort(int[] arr) { // 单向冒泡
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
static void bubbleSortOpt(int[] arr) { // 单向冒泡 + 有序后面无需冒泡
for (int i = 0; i < arr.length; i++) {
int flag = 0;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
swap(arr, j, j + 1);
flag = 1;
}
}
if (flag == 0) {
return;
}
}
}
static void bubbleSortOpt1(int[] arr) { // 单向冒泡 + 有序后面无需冒泡 + 部分有序部分无需冒泡
int pos = 0;
int end = arr.length - 1;
for (int i = 0; i < arr.length; i++) {
int flag = 0;
for (int j = 0; j < end; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
pos = j;
flag = 1;
}
}
end = pos;
}
}
static void bubbleSortOpt2(int[] arr) { // 双向冒泡 + 有序后面无需冒泡 + 部分有序部分无需冒泡
int start = 0;
int end = arr.length - 1;
int low = start;
int high = end;
for (int i = 0; i < arr.length; i++) {
int flag = 0;
for (int j = start; j < end; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
high = j;
flag = 1;
}
}
end = high;
for (int j = end; j > start; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
low = j;
flag = 1;
}
}
start = low;
if (flag == 0) {
return;
}
}
}
public static void main(String[] args) { // 主函数测试
int[] arr = new int[] { 21, 44, 77, 1, 6, 99 };
System.out.println(Arrays.toString(arr));
bubbleSortOpt2(arr);
System.out.println(Arrays.toString(arr));
}
感觉这个东西直接记住双向冒泡就可以了，毕竟是最优化的冒泡算法
