Array.prototype.sort是如何排序的？

这是我参与更文挑战的第1天，活动详情查看： 更文挑战

先看两个例子：

[2, 1, 12].sort(); 
// 结果并非[1, 2, 12] 而是 [1, 12, 2]
复制代码

var data = [
    {value: 2},
    {value: 1},
    {value: undefined},
    {value: 12},
    {value: undefined},
];

data
 .sort((x, y) => x.value - y.value)
 .map(x => x.value);
 // [1, 2, undefined, 12, undefined]
 
data
 .map(x => x.value)
 .sort((x, y) => x - y)
// [1, 2, 12, undefined, undefined]

// 先排序再取值 和 先取值再排序 得到的结果不一致
复制代码

为什么会出现非预期的排序结果呢？要知道原因，首先需要了解 Array.prototype.sort()方法。（答案见文末）

由于ECMA的规范中，并没有对sort方法使用哪种排序做出统一规定，因此每个浏览器都会给出自己的排序算法。
常见浏览器使用的排序算法如下：

要理解排序算法，首先需要理解几个概念：

稳定： 如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定： 如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。

时间复杂度: 一个算法执行所耗费的时间。

空间复杂度: 运行完一个程序所需内存的大小。

大O表示法： 一种表示算法运行时间的方法，O(n) 括号内的n指的是算法的操作数。

例如，列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间就是O(n)。

再例如，要在纸上画一个网格，包含16个格子。

算法1： 每次画一个格子，一共需要操作16次。用大O表示法就是 O(n)

算法2： 将纸对折4次，就可以得到16个格子。用大O表示法就是 O(log n)

常用的时间复杂度所耗费的时间：

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，例如快速排序。
• O(n²)，例如选择排序。
• O(n! )，例如旅行商问题的解决方案。

上面提到的浏览器用到的排序算法具体情况如下：

下面详细了解一下这四种排序方法，可以参考排序动画来理解：

math.hws.edu/eck/js/sort…

快速排序（Quick Sort）

简介：

快速排序的基本思想：分而治之。通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

步骤：

1. 从数列中挑出一个元素，称为”基准”（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

图解：

JS实现：

function quickSort(arr) {
 const pivot = arr.shift();
 const left = [];
 const right = [];
 
 if (arr.length < 2) {
    return arr;
 }
 
 arr.forEach((element) => {
    element < pivot ? left.push(element) : right.push(element);
 });
 
 return quickSort(left).concat([pivot], quickSort(right));
}
复制代码

归并排序（Merge Sort）

简介：

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略，以折半的方式来递归/迭代排序元素，利用空间来换时间，做到了时间复杂度 O(n·log(n)) 的同时保持了稳定。

分治法：将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。

步骤：

1. 将数组从中间分开，对两边分别排序；
2. 将两个有序的数组进行合并。

图解：

JS实现：

function mergeSort(arr) {
 const len = arr.length;
 
 if (len < 2) {
    return arr;
 }
 
 const mid = Math.floor(len / 2);
 const left = arr.slice(0, mid);
 const right = arr.slice(mid);
 
 return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
 const result = [];
 
 while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
 }
 
 return result.concat(left, right);
}
复制代码

插入排序（Insertion Sort）

简介：

默认 a[0] 为已排序数组中的元素，从 arr[1] 开始逐渐往已排序数组中插入元素，从后往前一个个比较，如果待插入元素小于已排序元素，则已排序元素往后移动一位，直到待插入元素找到合适的位置并插入已排序数组。

理解插入排序有一个很简单的方法，就是想象生活中打扑克牌的时候，每新摸到一张牌，就会按照大小把它插入之前的牌堆中。

步骤：

1. 从第二个元素开始，依次与前面的元素比较；
2. 如果小于前面的元素，则交换位置；
3. 经过n-1次循环，得到一个已排序数组。

图解：

JS实现：

function insertionSort() {
 let j, temp;
 for (var i = 1; i < array.length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && temp < array[j - 1]) {
        array[j] = array[j - 1];
        j--;
    }
    array[j] = temp;
 }
};
复制代码

桶排序（Bucket Sort）

简介：

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

步骤：

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

图解：

JS实现：

function bucketSort(array, num) {
 if (array.length <= 1) {
    return array;
 }
 var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;
 num = num || ((num > 1 && regex.test(num)) ? num : 10);
 for (var i = 1; i < len; i++) {
    min = min <= array[i] ? min : array[i];
    max = max >= array[i] ? max : array[i];
 }
 space = (max - min + 1) / num;
 for (var j = 0; j < len; j++) {
    var index = Math.floor((array[j] - min) / space);
    if (buckets[index]) { // 非空桶，插入排序
        var k = buckets[index].length - 1;
        while (k >= 0 && buckets[index][k] > array[j]) {
            buckets[index][k + 1] = buckets[index][k];
            k--;
        }
        buckets[index][k + 1] = array[j];
    } else { //空桶，初始化
        buckets[index] = [];
        buckets[index].push(array[j]);
    }
 }
 while (n < num) {
    result = result.concat(buckets[n]);
    n++;
 }
 return result;
}
复制代码

了解完这几种算法，回到最开始的问题，为什么12会小于2？为什么undefined的位置不固定？

查看Chrome使用的V8引擎源码可以发现如下两段关键代码：
源码地址

// 定义比较函数
comparefn = function (x, y) {
  if (x === y) return 0;
  if (%_IsSmi(x) && %_IsSmi(y)) {
    return %SmiLexicographicCompare(x, y);
  }
  x = TO_STRING(x); // <----- 注意这里
  y = TO_STRING(y); // <----- 注意这里 "12" < "2" => true
  if (x == y) return 0;
  else return x < y ? -1 : 1;
};
……
 
 
// 插入排序
function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i];
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j];
      var order = comparefn(tmp, element);
      if (order > 0) {
        // <---- 注意这里 2 - undefined => NaN
        a[j + 1] = tmp;
      } else {
        break;
      }
    }
    a[j + 1] = element;
  }
}
 
……
 
var num_non_undefined = %RemoveArrayHoles(array, length);
 
 
if (num_non_undefined == -1) {
  // There were indexed accessors in the array.
  // Move array holes and undefineds to the end using a Javascript function
  // < ----注意这里，排序之前会把数组里面的 undefined 移动到最后
  // that is safe in the presence of accessors.
  num_non_undefined = SafeRemoveArrayHoles(array);
}
复制代码

第一个问题，是因为比较函数中有TO_STRING方法，会将数字转换为字符串，导致”12″<“2″成立。

第二个问题，是因为简单数组在排序之前，会通过 SafeRemoveArrayHoles 方法将数组中的 undefined 移动到末尾。而对象数组则不存在这个情况，所以 undefined 会保持原位置。