资讯专栏INFORMATION COLUMN

简明算法: 冒泡排序(javascript描述)

liukai90 / 2473人阅读

懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。

(所有范例一律从小到大排序)

冒泡排序

给定数组:

var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];

算法描述:

将第一个元素与第二个元素对比,此时第一个元素比第二个元素大,交换他们,这样较大的元素就位于第二个位置了;

list = [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ];

将第二个元素与第三个元素对比,此时第二个元素比第三个元素小,保持原样不变;

list = [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ];

重复上面的步骤,直到最后我们用倒数第二个元素与倒数第一个元素相比之后,经过第一轮排序,最大的元素93被移动到了数组最后;

list = [ 26, 54, 17, 77, 31, 44, 88, 55, 20, 93 ];

然后我们重复1,2,3步骤;经过第二轮我们会找到次大的元素排在倒数第二位,即88被移动到了数组倒数第二位;

list = [ 26, 17, 54, 31, 44, 77, 55, 20, 88, 93 ];

再次重复直到整个数组有序;

第1轮: [ 26, 54, 17, 77, 31, 44, 88, 55, 20, 93 ]
第2轮: [ 26, 17, 54, 31, 44, 77, 55, 20, 88, 93 ]
第3轮: [ 17, 26, 31, 44, 54, 55, 20, 77, 88, 93 ]
第4轮: [ 17, 26, 31, 44, 54, 20, 55, 77, 88, 93 ]
第5轮: [ 17, 26, 31, 44, 20, 54, 55, 77, 88, 93 ]
第6轮: [ 17, 26, 31, 20, 44, 54, 55, 77, 88, 93 ]
第7轮: [ 17, 26, 20, 31, 44, 54, 55, 77, 88, 93 ]
第8轮: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]
第9轮: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

算法实现:

function bubble(list) {
  // 开启length-1轮循环,因为最后一轮只剩一个元素,没必要比较
  for (let i = 0; i < list.length - 1; i++) {
    // 两两对比,每次循环时j的取值上限需要舍去尾部已经有序的数据,所以length-1-i
    for (let j = 0; j < list.length - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        // ES6语法 交换元素
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
      }
    }
  }
}

// 测试
var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];
bubble(list);
console.log(list);
// [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

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

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

相关文章

  • 简明算法: 选择排序(javascript描述)

    摘要:懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。所有范例一律从小到大排序选择排序比冒泡的改进是,不会频繁交换元素,而只是记录索引,最后再交换。 懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。 (所有范例一律从小到大排序) 选择排序比冒泡的改进是,不会频繁交换元素,而只是记录索引,最后再交换。 选择排序 给定数组: var list = [ 54, 26, 93...

    Miyang 评论0 收藏0
  • 简明算法: 插入排序(javascript描述)

    摘要:懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。所有范例一律从小到大排序插入排序的思路可以参考抓扑克牌假定我们已有的扑克牌已经有序,现在抓了一张新牌,我们需要插入到适当的位置以保持队列依然有序。 懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。 (所有范例一律从小到大排序) 插入排序的思路可以参考抓扑克牌:假定我们已有的扑克牌已经有序,现在抓了一张新牌,我们需要...

    Guakin_Huang 评论0 收藏0
  • 算法排序算法总结(JavaScript描述

    摘要:二代码简单选择排序一分析循环次,每一次的当前项与其之后的项作比较,找出其中最小的那个,与当前项交换。二代码希尔排序是一种改进版的插入排序,缩小增量排序。这样做的目的是因为,直接插入排序在序列基本有序时效率最高。 排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 简单选择排序 O(n^2) O(n^2)...

    dkzwm 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

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

    canger 评论0 收藏0
  • 常用排序算法JavaScript实现

    摘要:代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序,排序的速度快于任何比较排序算法。 赞助我以写出更好的文章,give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它...

    jerry 评论0 收藏0

发表评论

0条评论

liukai90

|高级讲师

TA的文章

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