JavaScript 排序算法(JavaScript sorting algorithms)

JavaScrip 排序算法(JavaScript Sorting Algorithms)

基础构造函数

以下几栽排序算法做吧艺术在构造函数里。

function ArrayList () {
  var array = [];

  // 交换位置
  var swap = function (index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
  }

  this.insert = function (item) {
    array.push(item);
  };

  this.toString = function () {
    return array.join();
  };

  this.val = function () {
    return array;
  }

  // 冒泡排序
  this.bubbleSort = function () {
    //etc
  }
}

1. 冒泡排序

冒泡排序比较任何两单相邻的起,如果第一只比较第二独十分,则交换其。

复杂度 O(n^2)。

代码

this.bubbleSort = function () {
  console.time('Bubble Sort');
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j+1]) {
        swap(j, j + 1);
      }
    }
  }
  console.timeEnd('Bubble Sort');
}

图解

ECMAScript 1

2. 抉择排序

慎选排序算法是相同种原址比较排序算法。选择排序大致的思路是找到数据结构中的极小值并拿该放于第一各项,接着找到第二稍之价并拿其在第二个,以此类推。

复杂度:O(n^2)。

代码

this.selectionSort = function () {
  console.time('selectionSort');
  var length = array.length,
      indexMin;

  for (var i = 0; i < length - 1; i++) {
    indexMin = i;
    for (var j = i; j < length; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j;
      }
    }

    if (i !== indexMin) {
      swap(i, indexMin);
    }
  }
  console.timeEnd('selectionSort');
}

图解

ECMAScript 2

3. 插入排序

插入排序每次排一个频繁组项,以此方式构建最后之排序数组。假定第一桩已经排序了,接着,它和第二件进行比较,第二码是该要在原位还是栽到第一桩前为?这样,头片项就已正确排序,接着与老三码于(它是拖欠插到第一、第二尚是第三之位置为?),以此类推。

排序小型数组时,此算法比选排序和冒泡排序性能要好。

代码

this.insertionSort = function () {
  console.time('insertionSort');
  var length = array.length,
      j, temp;

  for (var i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && array[j-1] > temp) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = temp;
  }
  console.timeEnd('insertionSort');
}

图解

ECMAScript 3

4. 归并排序

由并排序是平种分治算法。其思想是用原始数组切分成较小的往往组,直到每个微数组只发一个职位,接着以小数组归并变成于生的多次组,直到最终才出一个排序完毕的命组。

复杂度:O(n log^n)。

代码

this.mergeSort = function () {
  console.time('mergeSort');
  array = mergeSortRec(array);
  console.timeEnd('mergeSort');
}
var mergeSortRec  = function (array) {
  var length = array.length;
  if (length === 1) {
    return array;
  }

  var mid = Math.floor(length / 2),
      left = array.slice(0, mid),
      right = array.slice(mid, length);

  return merge(mergeSortRec(left), mergeSortRec(right));
}
var merge = function (left, right) {
  var result = [],
      il = 0,
      ir = 0;

  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }

  while (il < left.length) {
    result.push(left[il++]);
  }

  while (ir < right.length) {
    result.push(right[ir++]);
  }

  return result;
}

图解

ECMAScript 4

5. 迅速排序

由并排序一样,快速排序为动分治的道,将原始数组分为较小的数组(但它们并未像归并排序那样以它分割开)。

其的属性一般比其他的复杂度为O(n log^n)的排序算法要好。

复杂度:O(n log^n)。

代码

this.quickSort = function () {
  console.time('quickSort');
  quick(array, 0, array.length - 1);
  console.timeEnd('quickSort');
}

var quick = function (array, left, right) {
  var index;
  if (array.length > 1) {
    index = partition(array, left, right);

    if (left < index - 1) {
      quick(array, left, index - 1);
    }

    if (index < right) {
      quick(array, index, right);
    }
  }
};

// 划分过程
var partition = function (array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
      i = left,
      j = right;

  while (i < j) {
    while (array[i] < pivot) {
      i++;
    }

    while (array[j] > pivot) {
      j--;
    }

    if (i <= j) {
      swapQuickSort(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}

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

图解

ECMAScript 5
ECMAScript 6
ECMAScript 7
ECMAScript 8
ECMAScript 9

6. ECMAScript 排序

ECMAScript没有定义用谁排序算法,所以浏览器厂商可以活动去贯彻算法。例如,Mozilla
Firefox使用由并排序作为Array.prototype.sort的兑现,而Chrome使用了一个高效排序(下面我们会修之)的变体。

this.esSort = function () {
  console.time('esSort');
  var tempArray = [];
  tempArray = array.sort(function (a, b) {
    return a - b;
  });
  console.timeEnd('esSort');
  return tempArray;
}

特性测试

环境

  • OS:WIN10 64位

  • 浏览器:Google Chrome 60.0.3112.78

代码

/**
* 创建随机数组
* @param  {[type]} size [description]
* @return {[type]}      [description]
*/
function createNonSortedArray (size) {
  var array = new ArrayList();
  for (var i = size; i > 0; i--) {
    var tempNum = Math.random() * i >>> 0;
    array.insert(tempNum);
  }
  return array;
}

// 冒泡排序
(function () {
  var array = createNonSortedArray(500);
  array.bubbleSort(); // Bubble Sort: 2.625ms
  console.log(array.val());
}());


// 选择排序
(function () {
  var array = createNonSortedArray(500);
  array.selectionSort(); // selectionSort: 1.986083984375ms
  console.log(array.val());
}());

// 插入排序
(function () {
  var array = createNonSortedArray(500);
  array.insertionSort(); // insertionSort: 1.825927734375ms
  console.log(array.val());
}());

// 归并排序
(function () {
  var array = createNonSortedArray(500);
  array.mergeSort(); // mergeSort: 0.76416015625ms
  console.log(array.val());
}());


// 快速排序
(function () {
  var array = createNonSortedArray(500);
  array.quickSort(); // quickSort: 0.39111328125ms
  console.log(array.val());
}());


// ES排序
(function () {
  var array = createNonSortedArray(500);
  array.esSort(); // esSort: 0.34130859375ms
  console.log(array.val());
}());

有鉴于此,一般情况我们唯有需要采取JavaScript 提供的
Array.prototype.sort()
方法即可,浏览器(或宿主环境)会当底部以最优算法帮咱落实排序。

来源/参考

  • 《学习 javascript
    数据结构》
  • About the #sorting-algorithms
    series
  • https://github.com/benoitvallon/computer-science-in-javascript/tree/master/sorting-algorithms-in-javascript

转载请注明出处: http://blog.givebest.cn/javascript/2017/08/02/javascript-sorting-algorithms.html