【从 0 到 1 学算法】5.Bubble Sort 算法 - 下

2022-10-15
河南
本文字数：1722 字
阅读完需：约 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;        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

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

发布于: 15 分钟前阅读数: 5

原文链接:【http://xie.infoq.cn/article/4e3f31ce65ec42d68abc59674】。未经作者许可，禁止转载。

Geek_65222d

关注

还未添加个人签名 2022-09-09 加入

还未添加个人简介

发布

暂无评论

创作场景

【从 0 到 1 学算法】5.Bubble Sort 算法 - 下

算法代码示例

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

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

Geek_65222d

评论