冒泡排序学习总结
目录
1、算法描述
这里有一个无序数组，接下来我要用冒泡的方式对其进行排序，冒泡排序的关键是相邻的两个元素进行比较。
比如说刚开始索引 0 和 索引 1 进行比较，如果是前一个小于后一个，它的位置可以不动。
这里3是大于2的 所以交换位置。
然后比较索引 1 和 索引 2 ，3 比4小不用交换位置，后面的以此类推。
到这里我们就看到最大的7已经移到了数组的最后，相当于已经把最大的元素已经冒泡成功了，完成了一轮冒泡。
接下来就是重复这个排序的动作，直到所有元素排序完成。
2、算法实现
package com.jie.bubbling;
import java.lang.reflect.Array;
import java.util.Arrays;
/**
* @description:冒泡排序
* @author: jie
* @time: 2022/2/8 19:44
*/
public class Bubbling {
public static void main(String[] args) {
int[] a = {5,9,3,7,2,1,8,4};
//调用方法
bubble(a);
}
/**
* @description:实现
* @author: jie
* @time: 2022/2/8 19:48
*/
public static void bubble(int[] a){
//比较的次数等于i<数组a的长度-1
for (int j = 0; j < a.length-1; j++) {
//一轮冒泡 比较的次数等于i<数组a的长度-1
for (int i=0;i<a.length-1;i++){
//如果前一个元素大于后一个元素，就交换位置
if (a[i] > a[i+1]) {
//交换位置
swap(a,i,i+1);
}
}
System.out.println("第"+j+"轮冒泡"+Arrays.toString(a));
}
}
/**
* @description:排序方法
* @author: jie
* @time: 2022/2/8 19:46
*/
public static void swap(int[] a,int i,int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}测试结果：
这里初步实现了冒泡排序算法，但是还有很多优化的空间，我们继续往下看。
3、算法优化
3.1 减少内层循环比较次数
我们看上图可以发现，每一轮的冒泡都要比较6次，但是是不是每轮冒泡都需要比较6次呢？不是。
因为我们第一轮冒泡以后，最大的 9 已经冒泡成功了，那下一轮冒泡的时候 9 就不需要进行比较了，没有意义，因为9已经是最大了，所以第二轮冒泡要比一轮冒泡少比较一次，后面的以此类推。
所以我们现在改进一下，改进 方法也非常简单。
我们这里利用外层循环 j 这个变量，j 一开始是0,所以第一轮循环，它并不会影响我们的冒泡次数，但随着 j 不断的增长，第二轮冒泡的时候 在 a.length-1 的基础上再 -j , 这样就达到我们比较次数逐次递减的效果。
测试结果：
3.2 减少冒泡次数
细心的大家可能已经发现，其实我们在第4轮冒泡完成以后，数据已经有序了，那我们已经完全没有必要进行后续的两次冒泡。
如果我某一轮冒泡两个相邻元素比较比较，没有发生一次交换，说明它整个已经有序了，我们就可以根据这个有没有发生交换来进行判断。
代码：
package com.jie.bubbling;
import java.lang.reflect.Array;
import java.util.Arrays;
/**
* @description:冒泡排序
* @author: jie
* @time: 2022/2/8 19:44
*/
public class Bubbling {
public static void main(String[] args) {
int[] a = {5,9,3,7,2,1,8,4};
//调用方法
bubble(a);
}
/**
* @description:实现
* @author: jie
* @time: 2022/2/8 19:48
*/
public static void bubble(int[] a){
//比较的次数等于i<数组a的长度-1
for (int j = 0; j < a.length-1; j++) {
//是否发生交换 false==没有交换
boolean swapped = false;
//一轮冒泡 比较的次数等于i<数组a的长度-1
for (int i=0;i<a.length-1-j;i++){
//如果前一个元素大于后一个元素，就交换位置
if (a[i] > a[i+1]) {
//交换位置
swap(a,i,i+1);
//发生交换了 true
swapped = true;
}
}
// 如果这一轮冒泡结束了，没有发生交换，说明数组有序了，退出循环
if(!swapped){
break;
}
System.out.println("第"+j+"轮冒泡"+Arrays.toString(a));
}
}
/**
* @description:排序方法
* @author: jie
* @time: 2022/2/8 19:46
*/
public static void swap(int[] a,int i,int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}测试结果：
3.3 进一步优化
package com.jie.bubbling;
import java.lang.reflect.Array;
import java.util.Arrays;
/**
* @description:冒泡排序
* @author: jie
* @time: 2022/2/8 19:44
*/
public class Bubbling {
public static void main(String[] args) {
int[] a = {5,2,7,4,1,3,8,9};
//调用方法
bubble(a);
}
/**
* @description:实现
* @author: jie
* @time: 2022/2/8 19:48
*/
public static void bubble(int[] a) {
int n = a.length - 1;
while (true) {
// 表示最后一次交换索引位置
int last = 0;
for (int i = 0; i < n; i++) {
System.out.println("比较次数" + i);
//如果前一个元素大于后一个元素，就交换位置
if (a[i] > a[i + 1]) {
//交换位置
swap(a, i, i + 1);
//发生交换了 把 i 赋值给last
last = i;
}
}
n = last;
System.out.println("第轮冒泡" + Arrays.toString(a));
if (n == 0) {
break;
}
}
}
/**
* @description:排序方法
* @author: jie
* @time: 2022/2/8 19:46
*/
public static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可。
总结
文字描述：
- 依次比较数组中相邻两个元素大小，若 a[j] > a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后
- 重复以上步骤，直到整个数组有序
优化方式： 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可
腾讯云开发者
