专栏首页FEWYJavaScript实现冒泡排序

JavaScript实现冒泡排序

说明

对数组进行 冒泡排序 算是比较简单的,冒泡排序也是容易理解的一种排序算法了,在面试的时候,很可能就会问到。

实现原理

数组中有 n 个数,比较每相邻两个数,如果前者大于后者,就把两个数交换位置;这样一来,第一轮就可以选出一个最大的数放在最后面;那么经过 n-1(数组的 length - 1) 轮,就完成了所有数的排序。

好的,我们先来实现找数组中的最大数,并把他放到数组最后。

var arr = [3,4,1,2];
// 遍历数组,次数就是arr.length - 1
for (var i = 0; i < arr.length - 1; i++) {
    // 如果前一个数 大于 后一个数 就交换两数位置
    if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
}
console.log(arr)  // [3, 1, 2, 4]

我们能找到数组中最大的数,放到最后,这样重复 arr.length - 1 次,便可以实现数组按从小到大的顺序排好了。

var arr = [3,4,1,2];
// 遍历数组,次数就是arr.length - 1
for (var j = 0; j < arr.length - 1; j++) {
    // 这里 i < arr.length - 1 ,要思考思考合适吗?我们下面继续说
    for (var i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            var temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}
console.log(arr)  // [1,2,3,4]

虽然上面的代码已经实现冒泡排序了,但就像注释中提到的,内层 for 循环的次数写成,i < arr.length - 1 ,是不是合适呢? 我们想一下,当第一次,找到最大数,放到最后,那么下一次,遍历的时候,是不是就不能把最后一个数算上了呢?因为他就是最大的了,不会出现,前一个数比后一个数大,要交换位置的情况,所以内层 for 循环的次数,改成 i < arr.length - 1 -j ,才合适,看下面的代码。

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  for (var j = 0; j < arr.length - 1; j++) {
    // 这里要根据外层for循环的 j,逐渐减少内层 for循环的次数
    for (var i = 0; i < arr.length - 1 - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
  return arr;
}
bubbleSort(arr);

我们想下这个情况,当原数组是, arr = [1,2,4,3]; 在经过第一轮冒泡排序之后,数组就变成了 arr = [1,2,3,4]; 此时,数组已经排序完成了,但是按上面的代码来看,数组还会继续排序,所以我们加一个标志位,如果某次循环完后,没有任何两数进行交换,就将标志位 设置为 true,表示排序完成,这样我们就可以减少不必要的排序,提高性能。

完整代码

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  var max = arr.length - 1;
  for (var j = 0; j < max; j++) {
    // 声明一个变量,作为标志位
    var done = true;
    for (var i = 0; i < max - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
      }
    }
    if (done) {
      break;
    }
  }
  return arr;
}
bubbleSort(arr);

性能

时间复杂度: 平均时间复杂度O(n*n) 、最好情况O(n)、最差情况O(n*n) 空间复杂度: O(1) 稳定性:稳定

时间复杂度指的是一个算法执行所耗费的时间 空间复杂度指运行完一个程序所需内存的大小 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置

总结

1、外层 for 循环控制循环次数 2、内层 for 循环进行两数交换,找每次的最大数,排到最后 3、设置一个标志位,减少不必要的循环

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript数组去重—ES6的两种方式

    版权声明:本文为博主原创文章,欢迎转载,转载请注明出处。 https://blog.csdn...

    FEWY
  • 简单说 CSS的vertical-align

    vertical-align属性,是CSS属性中一个比较重要的属性,也是比较不好理解的一个。 我们今天就来说说它。

    FEWY
  • JavaScript 数组去重的多种方法原理详解

    数组去重,这是一个面试经常会遇见的问题,网上讲数组去重的文章也是特别的多,但是我们依旧来讲讲数组去重,这篇文章比较适合于接触过一段时间的JavaScript的初...

    FEWY
  • js排序算法

    山河木马
  • 2 :基本语法

    六月的雨
  • 关于数组名的使用

    你会发现使用printf将这两个指针打印出来后,两者的值是一样的,那么他们俩到底有什么区别呢?

    HeaiKun
  • 算法之数组和问题

    算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

    SecondWorld
  • js中push(),pop(),unshift(),shift()的用法小结

    大当家
  • 数组中重复的数

    先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。

    谭小谭
  • 数组中的第K个最大元素

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

    WindrunnerMax

扫码关注云+社区

领取腾讯云代金券