冒泡排序(以新手角度去分析思路)

112 阅读5分钟

刚接触编程,对算法不是太理解,下面把思路分享一下:

  • 通常在实际开发中会用到这种再普通不过的数组了
var arr = [4,0,20,11,5,1,6,30,14];

需求是:要求把这些很乱的数组通过排序来实现从小到大、从大到小来进行排列,这个就叫编程语言中的-->冒泡排序

  1. 首先冒泡排序一次只比较两个数字,并且这两个数字是相邻的。
  2. 即然排序嘛,是要用到循环和判断的
  3. 首先先来看代码:
var arr = [4,0,20,11,5,1,6,30,14];
//外面这层for是控制比较的轮数的
for (var i = 0; i < arr.length-1; i++) {
    //内层循环是控制每轮比较的次数的
    for (var j =0;j < arr.length-1-i) {
        //再来个判断,条件成立,交换下标(索引)值 
        if  (arr[j]>arr[j+1]) {
            //创建一个第三方变量
            var temp = arr[i];
            arr[i] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}
console.log('arr');
  • 下面分析代码:
  • 外循环
    • i < arr.length-1===== i <8
    • 因为循环遍历时,是从下标[0]开始遍历的。而i的初始值也要为0,他遍历时就和数组下标[0]相对应。再来说循环轮数:循环轮数==数组长度-1,可以自己口算一下,每次交换下标值的次数始终要少于数组长度,拿例子举例,他一共要循环8轮,记住是外循环8轮。
  • 内循环:
    • j=0,和i一样,对应的是数组[0]这个位置
    • j < arr.length-1-i=======0 < 8(数组长度9-1-i(0))
    • 所以从上面我们得知:
    • i = 0,是对应的下标[0],i < arr.length-1是控制外层循环的轮数
    • j = 0,是对应的下标[0],j <arr.length-1-i是控制每轮里面的交换次数
  • 判断过程:
    • arr[j] > arr[j+1] 含义是:j为下标[0],arr[j+1]==0+1=arr[1] 下标[0]大于下标[1]吗?
    • 看这张图:

  • 由上图我们得知:arr[j]是操作的由下标[0]为起始的值,arr[j+1]得出的值=下标[1],与下标[0]对比。
  • 每一次都是

得知原理,我们来看运行的步骤

每外循环一次(i < arr.length-1),内循环的元素交换次数也就少一次(j < arr.length-1-i)

  • 第一轮外循环:i =0

    • 内循环:j = 0; j < arr.length-1-i

      • 第一次排序:4和0比较,  4大于0,   调换位置               [0,4,20,11,5,1,6,30,14]
      • 第二次排序:4和20比较,4小于20, 不调换位置           [0,4,20,11,5,1,6,30,14]
      • 第三次排序:20和11比较,20大于11,调换位置            [0,4,11,20,5,1,6,30,14]
      • 第四次排序: 20和5比较,20大于5,调换位置               [0,4,11,5,20,1,6,30,14]
      • 第五次排序:20和1比较,20大于1,调换位置                [0,4,11,5,1,20,6,30,14]
      • 第六次排序:20和6比较,20大于6,调换位置                [0,4,11,5,1,6,20,30,14]
      • 第七次排序:20和30比较,20小于30,不调换位置         [0,4,11,5,1,6,20,30,14]
      • 第八次排序:30和14比较,30大于14,调换位置             [0,4,11,5,1,6,20,14,30]
  • 第二轮外循环:i = 1

    • 内循环:j = 1; j < arr.length-1-i
      • 第一次排序:0和4比较, 0小于4, 不调换位置            [0,4,11,5,1,6,20,14,30]
      • 第二次排序:4和11比较,4小于11, 不调换位置         [0,4,11,5,1,6,20,14,30]
      • 第三次排序:11和5比较,11大于5,调换位置             [0,4,5,11,1,6,20,14,30]
      • 第四次排序: 11和1比较,11大于1,调换位置            [0,4,5,1,11,6,20,14,30]
      • 第五次排序:11和6比较,11大于6,调换位置            [0,4,5,1,6,11,20,14,30]
      • 第六次排序:11和20比较,11小于20,不调换位置      [0,4,5,1,6,11,20,14,30]
      • 第七次排序:20和14比较,20大于14,调换位置        [0,4,5,1,6,11,14,20,30]

第n轮外循环....

也就是这么个思路,感觉哪里好像还没写完。但就是这个思路。再不懂的东西,反复看,将他拆解出来,你总会把他的原理搞清楚的。路还很长,有写得不对的地方,还请大佬们指教下。