简单的自我介绍

我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是冒泡排序的算法学习。
最近疫情封校，在宿舍学习效率太低了，非常惆怅，目前学一会就困，想睡觉。不知道uu们有什么办法啊，想摆烂又于心不忍，不摆烂学习效率又低！

算法代码示例

public static void main(String[] args) {
    int[] a = {5,2,7,4,1,3,8,9};
    int len = a.length;
    for(int i=0;i<len-1;i++){
        int cnt=0;
        System.out.println("第"+(i+1)+"趟");
        for (int j=0;j<len-i-1;j++){
            if(a[j]>a[j+1]){
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
            cnt++;
        }
        for (int k=0;k<len;k++)
            System.out.printf("%d ",a[k]);
        System.out.printf("比较次数:%d\n",cnt);
    }
}

结果：

第1趟
2 5 4 1 3 7 8 9 比较次数:7

第2趟
2 4 1 3 5 7 8 9 比较次数:6

第3趟
2 1 3 4 5 7 8 9 比较次数:5

第4趟
1 2 3 4 5 7 8 9 比较次数:4

第5趟
1 2 3 4 5 7 8 9 比较次数:3

第6趟
1 2 3 4 5 7 8 9 比较次数:2

第7趟
1 2 3 4 5 7 8 9 比较次数:1

可以看出无优化版本和我们的推理一模一样

对算法进行更好的优化情况1

优化的方向：观察上述例子 我们可以看出主要问题在于当完全排序后 趟数并没有随之停止而是继续比较了三趟，针对这个问题我们有了这个思路：不难想到 在完全排序后 每趟中 必不可能出现交换的情况 因为以及有序了 相邻元素 都不满***换情况 所以我们只有判断如果 一次交换都没有 则可以证明 完全排序了

public static void main(String[] args) {
    int[] a = {5,2,7,4,1,3,8,9};
    int len = a.length;
    for(int i=0;i<len-1;i++){
        int cnt=0;
        boolean flag=false;// 判断是否有交换
        System.out.println("第"+(i+1)+"趟");
        for (int j=0;j<len-i-1;j++){
            if(a[j]>a[j+1]){
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
                flag=true;
            }
            cnt++;
        }
        for (int k=0;k<len;k++)
            System.out.printf("%d ",a[k]);
        System.out.printf("比较次数:%d\n",cnt);
        if (!flag)
            break;
    }
}    

结果：

第1趟
2 5 4 1 3 7 8 9 比较次数:7
第2趟
2 4 1 3 5 7 8 9 比较次数:6
第3趟
2 1 3 4 5 7 8 9 比较次数:5
第4趟
1 2 3 4 5 7 8 9 比较次数:4
第5趟
1 2 3 4 5 7 8 9 比较次数:3
可以看出趟数减少了两次，但最后不是在第四趟停止的原因是 第四趟进行了交换 真正不交换是在第五次。

对算法进行更好的优化情况2

优化方向：这个问题的优化点在：例如 第一趟时 8 9 最开始就是最大的两个值 所以我们进行比较时最后的结果是7 8 9 第二趟我们再次比较 会把 7 8 再比较一次 但我们已经确定了 7 8 9就是最大的值了，所以我们的优化思路是 我们记录一下最后一一次交换的索引，比如 在第一趟排序时 最后交换的是7 3 也就是数组下标4 数组下标4后的元素都是排序好的 所以我们第二趟排序 只用比较到 数组下标4这个位置 也就是只需要比较4次 直接少了两次，如果最后的交换下标是0 说明我们排序完成。

因为我们的每趟需要比较的次数比先前少 导致我们的趟数也会随着减少，因为原来每一趟比较次数只是减少1次，而现在我们每趟减少的都>=1次所以趟数随之减少。

再理解：最后一次排序一定是当前趟数的最大值 且 之前趟数一定都已经排好了 所以我们才能 下一次才可以只需要比较到最后一次排序的那个位置

int[] a = {5,2,7,4,1,3,8,9};
int len = a.length;
int n=len-1;
int i=0;
while (true) {
    System.out.println("第"+(++i)+"趟");
    int pos=0;//临时记录最后交换的位置下标
    int cnt=0;
    for(int j=0;j<n;j++){
        if(a[j]>a[j+1]){
            int t = a[j];
            a[j] = a[j+1];
            a[j+1] = t;
            pos=j;
        }
        cnt++;
    }
    n=pos;//真正记录最后位置的下标
    for (int k=0;k<len;k++)
        System.out.printf("%d ",a[k]);
    System.out.printf("比较次数:%d\n",cnt);
    if (n==0)
        break;
}

结果：

第1趟
2 5 4 1 3 7 8 9 比较次数:7
第2趟
2 4 1 3 5 7 8 9 比较次数:4
第3趟
2 1 3 4 5 7 8 9 比较次数:3
第4趟
1 2 3 4 5 7 8 9 比较次数:2

可以看出我们的比较次数与排序趟数都减少很多