javascript Array.prototype.sort 排序浅谈

IMWeb前端团队

发布于 2017-12-29 17:51:28

1K0

发布于 2017-12-29 17:51:28

文章被收录于专栏：IMWeb前端团队IMWeb前端团队

每个 Array 的实例都自带sort 函数，本文对sort函数的用法做一些探讨。

基本用法

1.数组元素为字符串的排序：

var fruit = ['cherries', 'apples', 'bananas'];
fruit.sort();
// => ['apples', 'bananas', 'cherries']

无参数调用 sort 函数，默认是升序排列的，字母 a b c ，排序结果正确.

2.数组元素为数字的排序：

var array = [3,7,2,8,2,782,7,29,1,3,0,34];
array.sort();
// => [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]

咦，怎么顺序好像不对？数字应该按从小到大升序排列的啊。什么原因呢？通过查询 MDN 文档[^3]，文档里是怎么说的呢？

The default sort order is according to string Unicode code points.

默认排序规则是数组元素字符的 Unicode 编码排序的，也就是说数组元素会被当做字符串，然后按照字符串的 Unicode 编码进行升序排列。

3.带参数的sort调用

那么如何实现元素为数字的数组按照数值升序排列呢？通过传入自定义的函数进行相邻元素的比较。

在探讨排序自定义函数之前，我们回到之前不带参数的排序，在排序时进行的是字符编码大小的比较，我们自己写一个函数将字符转为 unicode

为后面观察方便起见，转换字符串后返回的unicode编码用一个数组表示，如下：

function array2unicode(arr){
  return arr.map(function(s){
           // 先转为字符串
           s = String(s);
           // 字符串拆分字符
           var chars = s.split('');
           // 将每个字符转为 unicode 编码
           return chars.map(function(c){
                    return c.charCodeAt(0);
                  });
         });
}
// 举例
var array = [12,2,13];
array2unicode(array);
// => [ [ 49, 50 ], [ 50 ], [ 49, 51 ] ]
//    [     12        2         13     ]

4.sort排序过程模拟

那么下面来模拟内部的排序过程

var array;
array = [12,2,13];
// 将 array 的元素转为 unicode 编码
array2unicode(array);
// 对应关系如下：
//    [     12        2         13     ]
// => [ [ 49, 50 ], [ 50 ], [ 49, 51 ] ]
// 容易得出升序的排列结果为
//    [     12          13        2    ]
// => [ [ 49, 50 ], [ 49, 51 ], [ 50 ] ]

// 验证一下
[12,2,13].sort();
// => [12, 13, 2]

如果传入一个比较函数作为参数，如何实现默认的字符串排序效果呢？

[12,2,13].sort(function(a,b){
  a = String(a);
  b = String(b);
  if (a < b){
    return -1;
  }else if(a > b){
    return 1;
  }else{
    return 0;
  }
});
// => [12, 13, 2]

上面是 sort 函数内部按照字符unicode编码排序，关键的关键在于返回 -1 0 1，那么对于数字数组而言，我们更希望是按照数值进行排序，我们看到很多 js 代码中对数字进行排序的自定义函数如下：

[12,2,13].sort(function(a,b){
  return a - b;
});
// => [2, 12, 13]

5.带函数参数的sort排序规则的总结

sort 函数参数有两个，a、b，表示相邻的两个数组元素：

[12,2,13].sort(function(a,b){
  return a - b;
});

a - b 的值有三种情况

小余 0 时，a 排在 b 前面
大余 0 时，a 排在 b 后面
等余 0 时，a b 的相对位置保持不变

6.注意项

上面说到，sort 函数参数返回值可能有 3 个，那么下面的写法是错误的：

arr.sort(function(a,b){
  return a<b;
});
// 可能的结果 => [21, 0, 3, 11, 4, 5, 6, 7, 8, 9, 10, 1, 2, 12, 
//               13, 14, 15, 16, 17, 18, 19, 20, 22]
// 不是正确的结果，因为
// return a<b;
// 只返回了两种值 true false 相当于 1 0 ，而没有 -1

Array.prototype.sort 的内部实现 [^1]

Quicksort is generally considered to be efficient and fast and so is used by V8 as the implementation for Array.prototype.sort() on arrays with more than 23 items. For less than 23 items, V8 uses insertion sort[2]. Merge sort is a competitor of quicksort as it is also efficient and fast but has the added benefit of being stable. This is why Mozilla and Safari use it for their implementation of Array.prototype.sort().

chrome 对 sort 做了特殊处理，对于长度小余 23 的数组使用的是 insert sort ，大于 23 使用的是 quicksort. quicksort 是不稳定的排序算法 , 因此 Mozilla 和 Safari 采用了 merge sort 来实现. 由于所学有限，就不展开了。

关于什么是稳定排序(Stable)，wiki 上有张示意图很明白 [^2]：