冒泡排序 & 选择排序 & 插入排序 & 希尔排序 JavaScript 实现

之前用 JavaScript 写过 快速排序归并排序,本文聊聊四个基础排序算法。(本文默认排序结果都是从小到大)

冒泡排序

冒泡排序每次循环结束会将最大的元素 "冒泡" 到最后一位。

以 [1, 5, 2, 4, 3] 为例,O(n^2) 的复杂度,总共外层循环 5 次,第一次循环结束后的结果是 [1, 2, 4, 3, 5]。 首先是 1 和 5 比较,1 <=5,不交换位置,然后 5 和 2 比较,5 > 2,交换位置,数组变为 [1, 2, 5, 4, 3],然后 5 和 4 比较,交换位置,数组变为 [1, 2, 4, 5, 3],最后 5 和 3 比较,交换位置,数组为 [1, 2, 4, 3, 5],这个时候最大的元素 5 已经到了最后,整个交换过程中大的元素就好像 "冒泡" 一样冒出来。然后 [1, 2, 4, 3] 再进行同样操作,以此类推。

冒泡排序看起来无论最好情况还是最坏情况,复杂度一样,都是 O(n^2)。

function swap(array, a, b) {
  var tmp = array[a];
  array[a] = array[b];
  array[b] = tmp;
}

function bubbleSort(array) {
  var _array = array.concat();

  for (var i = 0, len = _array.length; i < len; i++)
    for (var j = 0; j < len - 1 - i; j++)
      if (_array[j] > _array[j + 1])
        swap(_array, j, j + 1);

  return _array;
}

var a = [1, 5, 2, 4, 3];
var ans = bubbleSort(a);
console.log(ans); // [1, 2, 3, 4, 5]

选择排序

选择排序每次循环会找到最值元素的下标,然后将该元素交换到最前面。所以选择元素每次循环交换一次,不会像冒泡一样多次交换。

还是以 [1, 5, 2, 4, 3] 为例,第一次循环比较,默认最值下标为 0,最值为 1,接着分别和 5,2,4,3 比较,ok 比完,最值的下标还是 0,那么就不交换(也可以看做 array[0] 和 array[0] 交换)。接着进行第二轮,是为 [5, 2, 4, 3] 进行循环,以此类推。

和冒泡相比,选择排序也是无论好坏情况,复杂度都是 O(n^2),而效率应该比冒泡稍微好点,毕竟交换次数少了。

function swap(array, a, b) {
  var tmp = array[a];
  array[a] = array[b];
  array[b] = tmp;
}

function selectionSort(array) {
  var _array = array.concat();

  for (var i = 0, len = _array.length; i < len; i++) {
    // 最值元素下标
    var index = i;

    for (var j = i + 1; j < len; j++)
      if (_array[j] < _array[index])
        index = j;

    swap(_array, i, index);
  }

  return _array;
}

var a = [1, 5, 2, 4, 3];
var ans = selectionSort(a);
console.log(ans); // [1, 2, 3, 4, 5]

插入排序

插入排序会比前面两种排序算法高效。它将数组分成 "已排序" 和 "未排序" 两部分,一开始的时候,"已排序" 的部分只有一个元素,然后将它后面一个元素从 "未排序" 部分插入 "已排序" 部分,从而 "已排序" 部分增加一个元素,"未排序" 部分减少一个元素。以此类推,完成全部排序。(摘自阮老师的博文 http://javascript.ruanyifeng.com/library/sorting.html

还是以 [1, 5, 2, 4, 3] 为例,外层还是需要循环 5 次,假设循环到第三次,到 2 这个元素,前面已经有序,是为 [1, 5],我们要将 2 插入,首先比较 5 和 2,交换,此时数组前三项为 [1, 2, 5],再比较 1 和 2,ok,不用交换了,有序了,比较结束。再看 4,第一次比较后,交换,数组为 [1, 2, 4, 5],然后 4 和 2 比较,ok,有序了,不用继续比了,那么 2 就不用和 1 比较了,这样就大大节省了相邻元素两两比较的次数。

和前两者相比,插入排序能减少比较次数,当然最坏情况下还是 O(n^2),但是和选择排序相比,可能会多交换次数。

function insertionSort(array) {
  var _array = array.concat();

  for (var i = 0, len = _array.length; i < len; i++) {
    // 储存当前位置的值
    var item = _array[i];

    // 和前面已经有序的部分,比较,交换
    for (j = i - 1; j > -1 && _array[j] > item; j--)
      _array[j + 1] = _array[j];

    _array[j+1] = item;
  }

  return _array;
}

var a = [1, 5, 2, 4, 3];
var ans = insertionSort(a);
console.log(ans); // [1, 2, 3, 4, 5]

当然,真实生产环境中不可能用这三种排序方法,毕竟效率太低!不过一定要比较效率的话,我觉得是 插入排序 > 选择排序 > 冒泡排序!

希尔排序

希尔排序是选择排序的升级版,可以说是分组插入排序,据说复杂度达到 O(n^1.2)。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

它是怎么排序的呢?我们设定一个变量叫做 gap,gap 小于数组长度,对于数组,我们将距离 gap 的元素划分为一组,每组进行插入排序,gap 不断变小,最后减为 1,即完成希尔排序。

gap 如何取值?有个简单一点的方法,第一次取值数组长度一半,然后再一半,再一半,最后为 1。当然如果要求更高效率,可以深入研究下 gap 的取值。至于希尔排序为什么效率会比普通的插入排序高,这点不在本文探讨范围之内(其实是我不知道),有兴趣的可以查阅相关资料。

// 希尔排序:先将整个待排序记录序列分割成若干个子序列
// 在序列内分别进行直接插入排序,待整个序列基本有序时,
// 再对全体记录进行一次直接插入排序
function shellSort(array){
  var len = array.length
    , gap = ~~(len >> 1); 

  // 克隆数组
  var result = array.concat();

  while (gap > 0) {
    for(var i = gap; i < len; i++) {

      var tmp = result[i];
      var j = i - gap;

      while (j >= 0 && tmp < result[j]) {
        result[j + gap] = result[j];
        j -= gap; 1
      }

      result[j + gap] = tmp;
    }

    gap = ~~(gap >> 1);
  }

  return result;
}

var a = [1, 5, 2, 4, 3];
var ans = shellSort(a);
console.log(ans); // [1, 2, 3, 4, 5]

Read More:

上一篇:构造persen


下一篇:你应该知道的基础 Git 命令