阅读 1134

一看就懂的冒泡排序和【3】步深度优化法

如需转载,请标明地址

前言:各位小伙伴们,冒泡排序作为我入门编程第一个遇到的算法,对我来说意义非凡。今天闲来重新拾起了这个算法,发现它竟然还有这么大的优化空间,惊讶。那我们就来优化一下它吧!写这篇文章呢主要是想和在座的各位小伙伴分享一下我的优化历程,二来还可以方便以后复习。废话不多说。我们直接开始吧!


相比大家对冒泡排序法还是不陌生的,如果你是刚刚接触编程也没关系,请看我慢慢给你解答!

基础比较好的小伙伴可以直接略过

什么是冒泡排序?


冒泡排序(Bubble Sort)是一种较简单的排序算法。

通过比较两个相邻数组元素来达到由大(xiao)到小(da)排序数组的目的

我这么说是不是能明白一点呢?不明白也没关系,就让我们一起来看代码吧!

int[] array = {
    9, 8, 7, 6, 5, 4, 3, 2, 1, 0
};
复制代码

这是一个0-9的倒序排列的数组,我们通过相邻元素的下标比对然后互换来完成从小到大的排序,如图:

这样我们就完成了将9放到了数组的最后。完成了一次排序。


怎么样,你是不是能明白了呢?

说到这里,那我们如何用代码来实现呢?

int[] array = {
    9, 8, 7, 6, 5, 4, 3, 2, 1, 0
};
// 一次遍历,将相对最大的数放到数组底部
for (int j = 0; j < array.length - 1; j++) {
    if (array[j] > array[j + 1]) {
        int max = array[j];
        array[j] = array[j + 1];
        array[j + 1] = max;
    }
}
复制代码

输出的结果: [8, 7, 6, 5, 4, 3, 2, 1, 0, 9]


那怎么完成所有元素的排序呢?

那就太好办了!再加一个循环吧!

int[] array = {
    9, 8, 7, 6, 5, 4, 3, 2, 1, 0
};
int max = 0;

// 一次遍历,在倒序情况下最少遍历的次数
for (int i = 0; i < arrays.length - 1; i++) {
    // 二次遍历,将相对最大的数放到数组底部
    for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
            max = array[j];
            array[j] = array[j + 1];
            array[j + 1] = max;
        }
    }
}
复制代码

输出结果: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


做到这里,我们发现了,这样的写法并不完美,有很多纰漏。大大影响了程序的性能。那我们应该怎么去优化呢?

我们的目的:

  • 增加循环效率
  • 减少无用的循环遍历和判断

最有用的办法就是观察算法的有效遍历数和实际遍历数


第一步优化

那我们就想办法先为程序减少一些循环吧!

我发现在执行二次遍历时,程序越运行到后面,所做的排序就越少,因为数组后面的元素都已排序完成,无需再进行循环判断

这样一想,我们的优化方案就有了!

一次遍历的计数(i)就相当于我们数组已经排好元素的个数

减去(i),就可以减少循环次数

int[] array = {
    9, 8, 7, 6, 5, 4, 3, 2, 1, 0
};
// 程序有效运行的次数
int runCount = 0;
// 一共遍历的次数
int allCount = 0;
int max = 0;

// 一次遍历,在倒序情况下最少遍历的次数
for (int i = 0; i < array.length - 1; i++) {
    // 二次遍历,将相对最大的数放到数组底部
    for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                max = array[j];
                array[j] = array[j + 1];
                array[j + 1] = max;
                runCount += 1;
        }
        allCount += 1;
    }
}
System.out.println("runCount = " + runCount);
System.out.println("allCount = " + allCount);
System.out.println(Arrays.toString(array));
复制代码

输出结果:

runCount = 45
allCount = 45
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

从结果来看,有效遍历和实际遍历次数相同。

但是这是在极端情况下(完全倒序),我们拿到的数组大多数情况都是无序散乱的。这样的优化明显不能满足我们的要求。这又为第二次优化提供了思路...


第二步优化

往往散乱的数组实际所需的遍历次数是远小于极端情况(完全倒序)的,然而我们程序还是会进行循环遍历.

那我们不如做个判断,判断它是否需要进行实际遍历,如果不需要了。那数组肯定是排序完成了!那我们就可以跳出循环了。

这样一想,我们的优化方案又有了!

我们用无序数组进行测试

int[] array = {
    3, 6, 2, 7, 9, 5, 0, 1, 4, 8
};
// 程序有效运行的次数
int runCount = 0;
// 一共遍历的次数
int allCount = 0;
int max = 0;
// flag判断排序是否完成 true-完成;false-未完成
boolean flag;

// 一次遍历,在倒序情况下最少遍历的次数
for (int i = 0; i < array.length - 1; i++) {
    // 每次循环重置flag为true
    flag = true;
    // 二次遍历,将相对最大的数放到数组底部
    for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                max = array[j];
                array[j] = array[j + 1];
                array[j + 1] = max;
                runCount += 1;
                // 进入循环表示数组未排序完成,需再次循环
                flag = false;
        }
        allCount += 1;
    }
    // 如果已经完成排序,则跳出循环
    if (flag) {
        break;
    }
    
}
System.out.println("runCount = " + runCount);
System.out.println("allCount = " + allCount);
System.out.println(Arrays.toString(array));
复制代码

输出结果:

runCount = 22
allCount = 42
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

未加判断输出结果:

runCount = 22
allCount = 45
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

从结果可以看出来,比未加判断的实际遍历次数少了3次。

但是优化到此为止好像还是缺了点什么,如果数组天生有一部分就是无需排序的,那我们又会浪费很多次的循环,这么一想,第三步优化就有了方向。


第三步优化

如图:

后面的 5 6 7 8 9 本来就是排序完成的,那按照我们的代码还要去对后面的代码进行循环遍历,那样是很不科学的!

这样一想,我们的优化方案就完美了!

我用几个变量来动态记录数组所需遍历的次数就可以解决问题了。

int[] array = {
    3, 6, 2, 7, 9, 5, 0, 1, 4, 8
};
// 程序有效运行的次数
int runCount = 0;
// 一共遍历的次数
int allCount = 0;
int max = 0;
// flag判断排序是否完成 true-完成;false-未完成
boolean flag;
// 无序数组循环边界,默认为数组长度array.length - 1
int sortBorder = array.length - 1;
//  记录数组最后进行排序的位置
int lastChange = 0;

// 一次遍历,在倒序情况下最少遍历的次数
for (int i = 0; i < array.length - 1; i++) {
    // 每次循环重置flag为true
    flag = true;
    // 二次遍历,将相对最大的数放到数组底部
    for (int j = 0; j < sortBorder; j++) {
            if (array[j] > array[j + 1]) {
                max = array[j];
                array[j] = array[j + 1];
                array[j + 1] = max;
                runCount += 1;
                // 进入循环表示数组未排序完成,需再次循环
                flag = false;
                // 记录数组最后进行排序的位置
                lastChange = j;
        }
        allCount += 1;
    }
    // 动态设置无序数组循环边界
    sortBorder = lastChange;
    // 如果已经完成排序,则跳出循环
    if (flag) {
        break;
    }
}
System.out.println("runCount = " + runCount);
System.out.println("allCount = " + allCount);
System.out.println(Arrays.toString(array));
复制代码

输出结果:

runCount = 22
allCount = 35
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

优化到这一步我们基本的需求就已经完成了,有效遍历和实际遍历次数已经相当接近了。

有的小伙伴会问了:怎么还是多出来 13 次啊?

我觉得在目前看来多于的次数对于有效遍历提供了一定的帮助,所以并不是完全无效的。

不懂的小伙伴可以复制代码进行 bebug 也可以直接问我。但是不要停止思考哦。说不定你就找出更好的优化方案了呢!

最后还是感谢各位小伙伴能够看到最后。文章有什么出错的地方欢迎指出改正。

关注下面的标签,发现更多相似文章
评论