JS-冒泡排序

2018-06-24 01:46:47来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

从开始排序算法之前,我们先创建一个方法用来生成原数组(指要被排序的数组)

function ArrayList() {
  var array = []; // {1}
  this.insert = function(item) {  // {2}
    array.push(item);
}
  this.toString = function() {  // {3}
    return array.join();
}

ArrayList是一个简单的数据结构,它将项储存在数组中(行 { 1 })。只需要向ArrayList里插入一个insert方法来向数据结构中添加元素(行{ 2 }),用array.push方法像数组中添加元素,最后用join方法来拼接数组中的所有元素来生成一个单一的字符串,方便在浏览器的控制台打印结果。

 

冒泡排序:时间复杂度为O(n^2)

比较任意两个相邻的项,如果第一个比第二个大,则交换它们,元素向上移动至正确的顺序,就好像气泡升至表面上一样。

冒泡排序是排序算法中最简单的,然而,从运行事件的角度来看,冒泡排序是最差的一个, 首先我们来讲解一下思路吧:

冒泡排序图解   

  

function ArrayList() {
  var array = []
  this.insert = function(item) {
    array.push(item)
  }
  this.toString = function() {
    return array.join()
  }

  /**
   * 冒泡排序
   */
  this.bubbleSort = function() {
    var length = array.length;                         //{1}
    for (var i = 0; i < length; i++) {                     //{2}
      for (var j = 0; j < length - 1; j++) {                //{3}      
        if (array[j] > array[j + 1]) {                    //{4}
          [array[j], array[j + 1]] = [array[j + 1], array[j]];     //{5}
        }
      }
    }
  }
}

这里为了让大家熟悉面向对象开发,所以选用了在构造函数里扩展方法的形式来编写代码

首先如行{ 1 }, 先声明一个名为length的变量,用来储存数组的长度;

接着如行{ 2 }, 从数组的第一位迭代至最后一位,他控制了在数组中经过多少轮排序(应该是数组中每项都经过一轮,轮数和数组的长度一致);

然后如行{ 3 }, 内循环从第一位迭代至倒数第二位, 因为内循环就不用和自己比较了直接与下一项比较, 所以遍历会少一位。

再如行{ 4 }, 内循环进行当前项与下一项的比较,如果当前项比下一项大,则交换它们 ( 如行{ 5 } )。

行{ 5 } 用到了ES6的解构赋值, 也可以封装一个函数来实现交换数组中的元素

如下:

function swap(array, index1, index2) {
  var aux = array[index1];
  array[index2] = array[index1];
  array[index1] = aux;          
}

*改进:

比如: 当外循环i=0; 第一个元素经过内循环找到了自己的对应位置, 那么i=1时, 就不必再去循环它了, 但上面的代码, 内循环还是把所有的项都遍历一遍, 显然是需要改进的。

this.modifiedBubbleSort = function() {
    var length = array.length;                         //{1}
    for (var i = 0; i < length; i++) {                      //{2}
      for (var j = 0; j < length - 1 - i; j++) {              //{3}      
        if (array[j] > array[j + 1]) {                    //{4}
          swap(array, j, j+1)                          //{5}
        }
      }
    }
  }

在行{ 3 }中, 我们把内循环遍历的条件改了, 这样内循环把外循环已经跑过的轮数去掉了, 就可以避免内循环中所有不必要的比较。

 

好了, 冒泡排序今天就介绍到这里, 最好画画图好好理解, 比较一下改进与改进之前的算法, 加深理解。

有问题可以评论呦~

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:谈谈前端异常捕获与上报

下一篇:前端性能优化