资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/冒泡排序算法

冒泡排序算法

CarterLi / 827人阅读

摘要：如下是一个基本的冒泡排序算法，执行的过程外部循环次内部循环每次用的值与的值进行比较由于外部循环的变量每次进入内部循环都不会改变，也就是的值进入内部循环后，都会以自身与也就是整个数组的所有元素比较一轮，结果是小于的数值都会被放到数组的开头经过

如下是一个基本的冒泡排序算法，执行的过程

外部循环len次

内部循环每次用arr[i]的值与arr[j]的值进行比较

由于外部循环的i变量每次进入内部循环都不会改变，也就是arr[i]的值进入内部循环后，都会以自身与arr[j]（也就是整个数组的所有元素）比较一轮，结果是小于arr[i]的数值都会被放到数组的开头

经过外层循环的一次次的进入内层循环的比对后，数组也依照从小到大的顺序排列了

let arr = [1, 3, 2]
let len = arr.length

for(let i = 0; i < len; i++){
    for(let j = 0; j < len; j++){
        if(arr[i] > arr[j]){
            let temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
}

我们来分解步骤

第一轮外层循环 i = 0
    第一轮内部循环 
    j = 0
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++， arr保持现状 [1, 3, 2]
    
    j = 1
    
    arr[i] = 1 arr[j] = 3 arr[i] > arr[j]不成立，j++, arr保持原样 [1, 3, 2]
    
    j = 2
    
    arr[i] = 1 arr[j] = 2 arr[i] > arr[j]不成立，j++, arr保持原样 [1, 3, 2]
    
    j = 3
    
    arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第一轮层循环结束

第二轮外层循环 i = 1
    第二轮内部循环
    j = 0
    
    arr[i] = 3 arr[j] = 1 arr[i] > arr[i]成立， arr[i]和arr[j]交换数值,arr更新为[3, 1, 2]
    
    j = 1
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原样 [3, 1, 2]
    
    j = 2
    
    arr[i] = 1 arr[j] = 2 arr[i] > arr[i]不成立，j++, arr保持原样 [3, 1, 2]
    
    j = 3
    
    arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第二轮层循环结束

第三轮外层循环 i = 2
    第三轮内部循环
    j = 0
    
    arr[i] = 2 arr[j] = 3 arr[i] > arr[i]不成立，j++, arr保持原样 [3, 1, 2]
    
    j = 1
    
    arr[i] = 2 arr[j] = 1 arr[i] > arr[i]成立, arr[i]和arr[j]交换数值,arr更新为[3, 2, 1]
    
    j = 2
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原样 [3, 2, 1
    
    j = 3
    
    由于众所周知的原因，第三轮内部循环结束

第四轮外层循环 i = 3

由于i < len不成立，外部循环结束，现在我们的数组最终结果为[3, 2, 1]
接下来我们来看看有没有优化的空间 
我们发现，每次内部循环都市从索引 let j = 0; 开始的，也就是说每次内部循环 arr[j]
都会把数组遍历一遍，由于在上一次的内部循环结束后，都会把最大的数放到数组的头部，所以再次进入内部循环时，如果还去从头比较就是浪费时间

所以如何让内部循环将上次列入最大值的位置忽略呢？

答案就是i变量,每次结束一次外部循环i变量都会加1，这也代表着有i个最大值被置于数组头部，也就是我们需要忽略的位置，所以，我们只需要将内部循环的起始位置i加上i，就可以将已经确定的位置忽略比较
for(let i = 0; i < len; i++){
    for(let j = 0 + i; j < len; i++){
        // 直接简写成let j = i也行
    }
}
然后我们来验证一下优化的成果

用一个大一点的数组，并且记录下循环次数

let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0

for(let i = 0; i < len; i++){
  for(let j = 0; j < len; j++){
    count++
    if(arr[i] > arr[j]){
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
}

console.log(arr, count)
arr = [324, 76, 65, 62, 56, 51, 45, 44, 43, 43, 34, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 0]
count = 1156次

下面看下优化过的

let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0

for(let i = 0; i < len; i++){
  for(let j = i; j < len; j++){
    count++
    if(arr[i] > arr[j]){
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
}

console.log(arr, count)
arr = [0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324]
595次

结果毋庸置疑减少了近半数的无用循环，那么到此为止了吗？
让我们再来看看
我们现在用的比较方式是基于用数组中的一个位置与所有位置进行比较，然后在下一轮比较时忽略已经确定的位置，
如下：
[1, 3, 2]

1 比 1

1 比 3

1 比 2

大家是不是发现了一个无效操作？就是1和1比较，这就是一个无效操作，由于外部循环的i和内部循环的j初始化会相等，所以arr[i]和arr[j]会取到同一个位置的值比较一次，那么怎么优化这个操作呢？

答案就是让内部j从第二位开始，避免和arr[i]取同一个值的情况

for(let i = 0; i < len; i++){
    for(let j = i; j < len - 1; j++){
       if(arr[i] > arr[j+1]){
           temp = arr[i];
           arr[i] = arr[j+1];
           arr[j+1] = temp;
       } 
    }
}

注意我给内部循环的len减去了1，是由于给j+1的会导致最后一次arr[j+1]会溢出数组，所以将其减1，正好弥补了j+1，也不会出现少遍历数组元素的情况

然后我们来看看成果

[0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324]
561次
私有云 混合云 冒泡排序 前端冒泡排序 冒泡排序代码 js冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/82602.html

相关文章

  • JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

    摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，...

    canger 评论0 收藏0

  • 数据结构与算法——冒泡排序

    摘要：多练练排序算法，不仅能够让我们知道一些排序方法的底层实现细节，更能够锻炼我们的思维，提升编程能力。排序算法的稳定性一个稳定的排序，指的是在排序之后，相同元素的前后顺序不会被改变，反之就称为不稳定。 1. 导言 因为这是排序算法系列的第一篇文章，所以多啰嗦几句。 排序是很常见的算法之一，现在很多编程语言都集成了一些排序算法，比如Java 的Arrays.sort()方法，这种方式让我们可...

    Yang_River 评论0 收藏0

  • 排序算法分析总结（附js实现）

    摘要：本文对一些排序算法进行了简单分析，并给出了的代码实现。平均时间复杂度不好分析，它是冒泡排序是稳定的排序算法。冒泡排序是原地排序算法原地排序指的是空间复杂度是的排序算法。归并排序，会将数组从中间分成左右两部分。 本文对一些排序算法进行了简单分析，并给出了 javascript 的代码实现。因为本文包含了大量的排序算法，所以分析不会非常详细，适合有对排序算法有一定了解的同学。本文内容其实不...

    liaoyg8023 评论0 收藏0

  • 数据结构与算法（二）：带你读懂冒泡排序（Bubble Sorting）

    摘要：经过一次冒泡排序，最终在无序表中找到一个最大值，第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环，而不会执行第二层循环。因此冒泡排序的时间复杂度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

    chuyao 评论0 收藏0

  • 算法之旅 | 冒泡排序法

    摘要：学堂码匠本期继续走入算法冒泡排序法。冒泡排序法完整代码冒泡排序法的优化假如序列的数据为使用上面的冒泡排序法进行排序，得到的结果肯定没有问题，但是，待排序的序列是有序的，理论上是无需遍历排序。 HTML5学堂-码匠：本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单，容易上手，稳定性也比较高,算是一种较好理解的算法，也是面试官高频提问的算法之一。 Tips：关于算法及排序的基础知识...

    qujian 评论0 收藏0

发表评论

登陆后可评论

0条评论

CarterLi

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<