转自：http://blog.cdswyda.com/post/javascript/2017-03-22-js-sort-not-only-bubblesort
做编程，排序是个必然的需求。前端也不例外，虽然不多，但是你肯定会遇到。
不过说到排序，最容易想到的就是冒泡排序，选择排序，插入排序了。
冒泡排序
依次比较相邻的两个元素，如果后一个小于前一个，则交换，这样从头到尾一次，就将最大的放到了末尾。
从头到尾再来一次，由于每进行一轮，最后的都已经是最大的了，因此后一轮需要比较次数可以比上一次少一个。虽然你还是可以让他从头到尾来比较，但是后面的比较是没有意义的无用功，为了效率，你应该对代码进行优化。
图片演示如下：
代码实现：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
选择排序
选择排序我觉得是最简单的了，大一学VB的时候，就只记住了这个排序方法，原理非常简单：每次都找一个最大或者最小的排在开始即可。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
动图演示：
代码演示：
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
插入排序也比较简单。就像打扑克一样，依次将拿到的元素插入到正确的位置即可。
1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
动图演示：
代码示例：
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
简单的代价是低效
上面三种都是非常简单的排序方法，简单的同时呢，效率也会比较低，还是拿这本书里的对比图来说明：
时间复杂度都高达O(n^2),而它们后面的一些排序算法时间复杂度基本都只有O(n log n)。
我的强迫症又犯了，我想要高效率一点的排序方法。
归并排序
简单把这本书的内容过了一遍，当时就理解了这个归并排序，因此这里就谈一下这个归并排序吧。
基本原理是分治法，就是分开并且递归来排序。
步骤如下：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤 3 直到某一指针达到序列尾；
5.将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示：
代码示例：
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
既然是个爱折腾的人，折腾了总得看看效果吧。
效率测试
由于我学这个来进行排序不是对简单数组，数组内都是对象，要对对象的某个属性进行排序，还要考虑升降序。
因此我的代码实现如下：
/**
* [归并排序]
* @param {[Array]} arr [要排序的数组]
* @param {[String]} prop [排序字段，用于数组成员是对象时，按照其某个属性进行排序，简单数组直接排序忽略此参数]
* @param {[String]} order [排序方式 省略或asc为升序 否则降序]
* @return {[Array]} [排序后数组，新数组，并非在原数组上的修改]
*/
var mergeSort = (function() {
// 合并
var _merge = function(left, right, prop) {
var result = [];
// 对数组内成员的某个属性排序
if (prop) {
while (left.length && right.length) {
if (left[0][prop] <= right[0][prop]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
} else {
// 数组成员直接排序
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left
.shift());
} else {
result.push(right.shift());
}
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
};
var _mergeSort = function(arr, prop) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return _merge(_mergeSort(left, prop), _mergeSort(right, prop), prop);
};
return function(arr, prop, order) {
var result = _mergeSort(arr, prop);
if (!order || order.toLowerCase() === 'asc') {
// 升序
return result;
} else {
// 降序
var _ = [];
result.forEach(function(item) {
_
