冒泡排序

什么是冒泡排序?

生活中,好奇的人们靠近池塘发现,鱼儿冒气泡,越往上气泡越大,似乎扔一块石头下去,也能有类似的效果。我们总结出一个规律就是从池塘底部到池塘表面它的气泡是由小到大排列的,诸如此类的排序,我们可以将其称之为冒泡排序。在计算机中,有意思的是,你可以选择性地操作数据,去让它实现由小到大或者由大到小地冒泡顺序。

Array.prototype.sort()这个API的排序原理是什么?

我们先看一个例子

const str_arr = ['2', '0', '1', '9', '19', '97', '6', '1', '3'];
const num_arr = [2, 0, 1, 9, 19, 97, 6, 1, 3];

// Array.prototype.sort
console.log('====Array.prototype.sort====');
console.log('str_arr sort before: %s', str_arr.toString());
console.log('str_arr sort after: %s', str_arr.sort().toString()); //str_arr sort after: 0,1,1,19,2,3,6,9,97
console.log('num_arr sort before: %s', num_arr.toString());
console.log('num_arr sort after: %s', num_arr.sort().toString()); //num_arr sort after: 0,1,1,19,2,3,6,9,97
console.log('====Array.prototype.sort====');

通过上面这个代码,猜也能猜到了,其内部实现的排序原理不是用数字比大小得到的,不然19就不会排在2前面。通过查阅相关资料,sort的默认排序顺序是将元素转换成字符串,然后比较它们的UTF-16代码单元值序列时构建的。

怎么办? 这肯定不是我想要的结果啊。

arr.sort([compareFunction]),sort这个函数支持传入一个比较函数,里面可以接受两个参数a和b,即用于比较的元素,如果大于0表示 b 会被排列到 a 之前, 如果等于0,表示a和b位置不变,如果小于0,表示a排在b前面。既然是这样,那事情就好办了。

const str_arr = ['2', '0', '1', '9', '19', '97', '6', '1', '3'];
const num_arr = [2, 0, 1, 9, 19, 97, 6, 1, 3];
// Array.prototype.sort: fix 0 相等、 -1 小于 1 大于
console.log('====Array.prototype.sort====');
console.log('str_arr sort before: %s', str_arr.toString());
console.log('str_arr sort after: %s', str_arr.sort((a, b) => a -b).toString()); //str_arr sort after: 0,1,1,2,3,6,9,19,97
console.log('num_arr sort before: %s', num_arr.toString());
console.log('num_arr sort after: %s', num_arr.sort((a, b) => a -b).toString()); //num_arr sort after: 0,1,1,2,3,6,9,19,97
console.log('====Array.prototype.sort====');

巧妙地解决了我们楼上遇到19排在2前面的问题,因为在做运算的时候,会被隐式转成Number类型进行,所有str_arr答案和楼下一样。

这里说明下这个API和今天要讲的冒泡排序没有半毛钱关系,只是在学习的时候当作拓展分享下心得,触类旁通,关于V8引擎对于这个API的实现,在数据量小于10的时候用的是插入排序,在数据量大于10的时候用的是快排,所有其本身是不稳定的排序,关于插入排序和快排,笔者会在后面的学习笔记中总结分享。

实现一个冒泡排序

需求: 实现一个冒泡排序算法,可以根据输入数据进行升序降序排列,输入的参数是一个数组arr和一个boolean类型的asc,默认为true。形如function bubble(arr, asc = true)

测试用例:[1, 9, 9, 7, 0, 6, 1, 3, 2, 0, 2, 0, 0, 7, 1, 6]

思路:我们可以这样子做,先思考下冒泡的逻辑,相邻两个元素,在升序情况下,如果前者比后者大,那么让其二者交换位置,反之相反。那么我们很容易想到了两层循环遍历的答案。

function bubble(arr, asc = true) {
  const len = arr.length;
  let tmp = null;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (asc && arr[i] > arr[j]) {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
      if (!asc && arr[i] < arr[j]) {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
    }
  }
}

这里说明下,我们其实有两种思路的,每遍历一次将最小的那位塞到左边,或者每遍历一次将最大的那位塞到右边,严格来说,把最大的塞到右边更符合常规的自然现象的逻辑思维,在这里笔者是用每次遍历将最小的那位塞到左边这种解决方案,当然啦,如果要实现每次冒泡把最大的那个塞到右边,程序还可以改造下,写波伪代码。

for (let i = 0; i < len; i++) {
    for (let j = 0; j < len -i -1; j++) {
        // code
}
}

关于两个数互换位置,笔者也是采用了最通用的创建一个临时变量的形式,以前学习C语言的课上,也有不用创建临时变量的方法,这个我们在问题思考的时候再讨论,先卖个关子,继续往下看吧。

如何优化冒泡排序?

写出上面的答案我们似乎看到胜利的苗头,嘿嘿嘿。那我们再从性能上看看有没有什么好的办法可以优化下的,两层遍历其算法复杂度为O(n^2),显然数据量大的时候不可取啊。其实在上面实现一个冒泡排序的时候,我们已经想到了,我们在上面做的事情是一次只冒一个泡泡,我们其实可以狠一点,一次冒两个啊,一次遍历的时候,我们就把最大的扔右边,最小的扔左边,遍历的范围逐步缩小,到底缩到什么时候停止呢?左边从0开始的标志位大于右边从最后一个元素开始的,那么我们就停。然后我们再思考下,思考一个踩着狗屎运的问题,就是一个特别恶心的测试用例,原来排序就已经是排好序的,那这样子我们就要设一个标志位,如果是这种情况(O(n))直接打回去。

function bubble(arr, asc = true) {
  let left = 0;
  let right = arr.length - 1;
  let flag = true;
  while (left < right) {
    for (let i = left; i < right; i++) {
      if (asc && arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        flag = false;
      }
      if (!asc && arr[i] < arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        flag = false;
      }
    }
    right--;
    for (let i = right; i > left; i--) {
      if (asc && arr[i] < arr[i - 1]) {
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
        flag = false;
      }
      if (!asc && arr[i] > arr[i - 1]) {
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
        flag = false;
      }
    }
    left++;
  }
  if (flag) return arr;
}

问题思考

冒泡排序的时间复杂度是多少?

踩着狗屎运刚好遇到已经排好序的情况下是O(n), 最差的情况需要二层循环遍历的时候是O(n^2)。

冒泡排序适用的场景是什么?

面试刷人、数据量不大,对性能要求不高

不增加参数、怎么互换a和b?

加减法(要考虑数字的取值范围,慎用)

a = a + b;
b = a - b;
a = a - b;

乘除法(要考虑数字的取值范围,慎用)

a = a * b;
b = a / b;
a = a / b;

注意除数不能为0。

位运算(异或, 慎用)

a = a ^ b;
b = a ^ b;
a = a ^ b;

当且仅当a = b时,炸,结果为0。

其他语言不晓得,ES6硬核的解构语法(推荐)

[a, b] = [b, a];

最后附上项目地址:https://github.com/ataola/JavaScript-Tsukuki/tree/master/code/sort

备注:在test文件夹下提供bubble.test.js(常规写法),bubble_good.test.js(优化写法),bubble_log.test.js(日志记录写法)。

参考文献

Array.prototype.sort(MDN): https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 选择排序

    最近看了一则寓言故事跟童鞋们分享一下,讲的是大山深处的神坑(为了激发大家的想象力,这里我就不画画了,请同学们自行脑补)。事情是这样子的,旁白站在上帝视角抛出一个...

    丰臣正一
  • JS面试押题(20190803)

    这周跟大家分享的面试题是“数组去重”。这种题目是个正经一点的厂一般在初试的时候都会让你做到的,频率相当高。曾经统计过差不多有8种不带重复的去重方法,但由于当时数...

    丰臣正一
  • 软件推荐(天若OCR) -- 文字识别,解放重复劳动

    今天是软件专场的倒数第90场,跟大家分享的是文字识别工具--天若OCR。下面我们把舞台交给天若OCR,大家掌声欢迎。

    丰臣正一
  • 选择排序

    选择排序的思想,每次从剩余元素中最小的元素与当前元素交换,第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换;第二次从arr[1]arr[n-...

    桑鱼
  • JavaScript常用排序算法

    3、对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

    FinGet
  • 团体程序设计天梯赛-练习集 L1-019 谁先倒

    划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为:每人口中喊出一个数字,同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和,谁...

    C you again 的博客
  • 数组中的第K个最大元素

    在未排序的数组中找到第k个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。

    WindrunnerMax
  • Js实现数组排序

    常用排序的Js实现方案,包括原型链方法调用、简单选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序。

    WindrunnerMax
  • golang数据结构之冒泡排序

    绝命生
  • 浙大版《C语言程序设计(第3版)》题目集 习题9-5 通讯录排序

    输入n个朋友的信息,包括姓名、生日、电话号码,本题要求编写程序,按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券