JS-冒泡排序

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

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

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}
        }
      }
    }
  }