前面的话

集中注意力到一个对象上,就像放大镜聚焦阳光一样……

冒泡排序是一个流行的算法,经常拿来作为教学使用,算作算法启蒙?

不过要彻底理解它还是得动点脑子的,对我而言感觉并不简单。一般上会有两个问题:一是专家盲点,老师因为太熟悉这个算法而无法想象初学者的疑惑,导致讲不明白;二是网上搜索“冒泡排序”所获取的信息良莠不齐,有些甚至都是错误的。

其实,我能模模糊糊理解这个算法的,但我是一个较真的人,想彻底钻透它,通过 “ 1+1=2” 这样的笨方法来彻底理解它。

本文以两个视频为基础:

  1. 【黑马JS教程-冒泡排序算法】(https://www。bilibili.com/video/BV1HJ41147DG?p=112)(避免直接解析出视频,请把。更换为.)(课程里的代码应该有点问题)
  2. 【狂神说Java-冒泡排序】(https://www。bilibili.com/video/BV12J41137hu?p=58)

个人理解

题目要求:将数组 arr1 = [3,4,5,2,1] ,从小到大排序(升序排序)。

  1. 针对这个数组,可以看到共有5个数,即 arr1.length = 5 ,如果这个数组有 N 个数,N 就是 arr1.length
  2. 首先相邻比较,筛选出最大数:【从第一个数字3开始:3和4比较、不动;4和5比较、不动;5和2比较、换位;5和1比较、换位;这样就筛选出了一个最大的数5】。
  3. 接下来是解决倒数第二大的数、倒数第三大的数、倒数第四大的数,当有4个数的位置被确定时,第五个数的位置也就确定了。
  4. 因此,如果一个数组的长度是 N ,那么通过这种【相邻比较】的方式,一共需要 N-1轮,(或者你也可以把轮说成趟,但要和下面的次数区分)。
  5. 接下来确定每轮需要两两比较的次数:5个数,如果要两两比较出最大值,需要相邻比较4次;4个数就是比较3次……,规律为:N-1。因为每一轮都会确定一个数,所以下一轮需要确定的数就为:N-轮数。(即第一轮,需要确定的数为5,需要比较4次;第二轮需要确定的数为4,需要比较3次;第三轮需要确定的数为3,需要比较2次;第四轮需要确定的数为2,需要比较1次。(纸上画一下比较容易理解))

第一轮-两两比较了4次:3和4比较、不动;4和5比较、不动;5和2比较、换位;5和1比较、换位。结果arr1 = [3,4,2,1,5]

第二轮-两两比较了3次:3和4比较、不动;4和2比较、换位;4和1比较、换位;4和5无需比较。结果arr1 = [3,2,1,4,5]

第三轮-两两比较了2次:3和2比较、换位;3和1比较、换位;3和4无需比较;4和5无需比较。结果arr1 = [2,1,3,4,5]

第四轮-两两比较了1次:2和1比较、换位;2和3无需比较;3和4无需比较;4和5无需比较。结果arr1 = [1,2,3,4,5]

找规律:如果一个数组的长度是 N ,那么每趟要比较的次数就是 N - 轮数

依据以上个人理解的代码实现

var arr1 = [3, 4, 5, 2, 1];
for (var i = 1; i < arr1.length; i++) { // 外层循环管趟数,执行n-1趟
    for (var j = 0; j <= arr1.length - i - 1; j++) { // 里面循环管每一轮的交换次数,执行n-i次。因为J要从数组中取值,因此需要从0开始;里面可以等价写为:j < arr1.length - i。
        // ↑大问题:假如是第一轮,虽然能循环4次,但j取不到arr1[4],这个肯定会出问题。在 Java 中验证这个问题。经验证后得知:j+1是可以取到4的,虚惊一场!
        // 前一个元素和后一个元素比较,如果前>后,则交换两个变量的值.
        if (arr1[j] > arr1[j + 1]) {
            var temp = arr1[j];
            arr1[j] = arr1[j + 1];
            arr1[j + 1] = temp;
        }
    }
}
console.log(arr1);

对黑马JS课堂上代码的分析

var arr1 = [3,4,5,2,1];
for (var i = 0; i <= arr1.length - 1; i++) { // 外层循环管轮数,5个数需要4轮,这都五轮了!)
    for (var j = 0; j <= arr1.length - i - 1; j++) { // 里层循环管每一轮的交换次数
        // 前一个元素和后一个元素比较,如果前>后,则交换两个变量的值.
        if (arr1[j] > arr1[j + 1]) {
            var temp = arr1[j];
            arr1[j] = arr1[j + 1];
            arr1[j + 1] = temp;
        }
    }
}
console.log(arr1);
  1. 第2行错误:应为 (var i = 0; i < arr1.length -1; i++), 去掉 = 号, 才是4轮。外层管轮数,无需从 0 开始,从 1 开始就好了,从0开始会大大增加理解这个算法的难度,让初学者困惑。
  2. 内层循环管每一轮的交换次数,次数为N - 趟数,即var j = 1; j <= arr1.length -i; j++,因为数组的索引从0开始,因此写为var j = 0; j <= arr1.length -i - 1; j++

    • 注意,j 能不能从1开始取值呢?是可以的!只要我们在写交换代码的时候,写成j-1j比较即可。
  3. 我现在都还记得这门课上,细节之处出现了很多错误,加重了学生的负担。

Java 实现

import java.util.Arrays; // 引入类库
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr ={3,4,2,5,1,100};
  
        System.out.println(Arrays.toString(bubbleSort(arr))); // 打印输出数组内元素

    }
    // 创建一个排序方法
    public static int[] bubbleSort(int[] arrays){
        for (int i = 1; i <arrays.length ; i++) {
            for(int j=0;j<arrays.length-i;j++){
                int temp = 0;
                if(arrays[j]>arrays[j+1]){
                    temp = arrays[j];
                    arrays[j]=arrays[j+1];
                    arrays[j+1]=temp;
                }
            }
        }
        return arrays;
    }
}

简谈一个数学基础

问:0到5有几个数字?1到5有几个数字?1到5有几个间隔?

答:6个;5个;4个;

从小到大,我连这个都没弄清楚,我都不知道我怎么学习的,怎么考上大学的!!

后记

  • 2020年5月12号,写成此文。
  • 2021年2月5号,使用 Java 重现冒泡排序,并对文章进行修改完善。标题《关于”冒泡排序“的再思考》——>《没有人比我更懂“冒泡排序”》
如果觉得我的文章对你有用,请随意赞赏