码云笔记前端博客
Home > JavaScript > 前端开发必会的JS算法之冒泡排序

前端开发必会的JS算法之冒泡排序

2019-10-28 分类:JavaScript 作者:管理员 阅读(64)

本文共计1414个字,阅读时间预计4分钟,干货满满,记得点赞加收藏哦

很多做前端开发的小伙伴都有这样的情况,对于JS的一些经典算法,在学时都觉得很清楚,当时也确实学会了,小手啪啪不在话下,然后过一阵子就会遗忘了,再让他动手写就显得很生疏,甚至哪儿学的还到哪儿去。所以,本系列文章就尝试解决这个问题。

比如冒泡排序就很形象,遍历n次,每次循环相邻元素两两比较,把其中大的元素往后放。例如:
前端开发必会的JS算法之冒泡排序
上图演示了冒泡过程的第一次循环。其中,最大的元素5就像气泡一样逐步上升到最后一位。

通过上图的演示过程我再用代码翻译出来:

1
2
3
4
5
6
7
let array = [5, 4, 3, 2, 1]
for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i+1]) {
    swap(array, i, i+1)
  }
}
console.log(array) // [4, 3, 2, 1, 5]

其中swap函数封装了两个元素如何交换:

1
2
3
function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}

第一次遍历会把最大的元素放到倒数第一个位置上,第二次遍历会把第2大的元素放倒数第二个位置上。
前端开发必会的JS算法之冒泡排序
其余次数,以此类推。此时,我们也很容易把这n次遍历写出来:

1
2
3
4
5
6
7
for (let j = 0; j < array.length; j++) {
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] > array[i+1]) {
      swap(array, i, i+1)
    }
  }
}

上述代码,还有优化的空间,比如第2次遍历时,元素4和5其实是不需要再比较的。因为上一次已经把未排好序中最大的数据挑走了。查看完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const utils = {
  swap(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
  },
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function bubbleSort(array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length -1 - i; j++) {
      if (array[j] > array[j + 1]) {
        utils.swap(array, j, j + 1)
      }
    }
  }
  return array
}
const array = bubbleSort(utils.randomArray())

console.log(array)

至此,冒泡排序原理和实现已经说完了。

这里总结一下,冒泡排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为O(n^2),适用于少量数据排序,但实际中用得不多。

冒泡排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是相邻两两比较,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。

以上就是前端开发必会的JS算法之冒泡排序的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持码云笔记!

「除特别注明外,本站所有文章均为码云笔记原创,转载请保留出处!」

赞(11) 打赏

觉得文章有用就打赏一下文章作者

支付宝
微信
11

觉得文章有用就打赏一下文章作者

支付宝
微信

上一篇:

下一篇:

你可能感兴趣

共有 0 条评论 - 前端开发必会的JS算法之冒泡排序

博客简介

码云笔记 mybj123.com,一个专注Web前端开发技术的博客,主要记录和总结博主在前端开发工作中常用的实战技能及前端资源分享,分享各种科普知识和实用优秀的代码,以及分享些热门的互联网资讯和福利!码云笔记有你更精彩!
更多博客详情请看关于博客

精彩评论

站点统计

  • 文章总数: 476 篇
  • 分类数目: 13 个
  • 独立页面: 8 个
  • 评论总数: 228 条
  • 链接总数: 15 个
  • 标签总数: 1050 个
  • 建站时间: 525 天
  • 访问总量: 8647866 次
  • 最近更新: 2019年11月21日