JavaScript数组排序方法sort()深层探究

—— sort()方法的算法分析及奇怪现象总结

momo314相同方式共享非商业用途署名转载

案发现场还原

今天突然发现之前写的一个javascript数组排序的功能出问题了,如下:

简化版案发现场:

//对一个由 A0 至 A9 共10个元素组成的乱序数组进行排序
var source = ['A7', 'A6', 'A0', 'A8', 'A5', 'A3', 'A4', 'A1', 'A9', 'A2'];
source.sort(function(a, b){
    return a > b;
});

/*
 *    结果为:
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"]
 */
//对一个由 A0 至 B0 共11个元素组成的乱序数组进行排序
var source = ['A7','A6','A0','A8','A5','A3','A4','A1','A9','A2','B0'];
source.sort(function(a, b){
    return a > b;
});

/*
 *    结果为:
 *    ["A3", "A7", "A0", "A2", "A5", "A6", "A4", "A1", "A8", "A9", "B0"]
 */

怎么样!怕不怕!!!服不服!!!不管你服不服,我反正是怕了。。。

案件规律分析及总结:

经过反复测试:

  1. 当数组长度小于等于10的时候,有参数的 .sort(sortby) 方法排序正常;
  2. 当数组长度大于10的时候,有参数的 .sort(sortby) 方法排序会出现错乱;
  3. 当有参数的 .sort(sortby) 方法排序出现错乱时,多次执行该方法每次的结果都不相同;
  4. 不论数组长度多长,无参数的 .sort() 方法排序始终正常。

.sort() 方法定义及排序错误的解决方案

.sort() 方法用于对数组的元素进行排序。

语法

arrayObject.sort(sortby)
参数 描述
sortby 可选。规定排序顺序。必须是函数。

返回值

对数组的引用。请注意,数组在原数组上进行排序,不生成副本。

说明

如果调用该方法时没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,是按照字符编码的顺序进行排序。要实现这一点,首先应把数组的元素都转换成字符串(如有必要),以便进行比较。

如果想按照其他标准进行排序,就需要提供比较函数,该函数要比较两个值,然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b,其返回值如下:

  • 若 a < b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值。
  • 若 a == b,则返回 0。
  • 若 a > b,则返回一个大于 0 的值。

解决方案

那么,其实看完定义,聪明的小伙伴就已经知道为什么我们的排序会出现错误了:

.sort() 方法规定,作为其参数的 function(a, b) 的返回值必须为数值类型(负数、0、正数分别代表a < b、a == b和a > b)

而我们在上面的代码中返回的确是 bool 类型,这显然是不对的,bool类型只有true/false两个值,怎么可能表达出 大于/小于/等于 3种状态呢。大家都知道在js里面 true == 1 false == 0 这两个表达式是成立的,也就是说,在上面的错误代码中,虽然本意可能是说返回false就代表 a < b,但实际执行起来程序却会认为 a == b,这也就是排序结果错误的原因。

所以,其实正确的代码应该是这样的:

source.sort(function(a, b){
    if(a == b)
        return 0;
    return a > b ? 1 : -1;
});

事实证明,这样确实已经可以得到正确的排序结果了,不论数组长度有多长,结果都是正确的。

.sort() 方法深层探究[1]: 排序算法分析

为了分析javascript中的.sort() 方法中使用的排序算法,我们可以在sortby函数内加上一些日志,如下:

代码、执行日志及日志分析内容较长,可以直接看后面的分析结果。

var source = ['A1', 'A9', 'A0', 'A5', 'A3', 'A2', 'A7', 'A8', 'A4', 'A6'];

var sortby = function (a, b) {
    console.log(source);
    console.log('-----------------------------------------------------------');
    console.log('compare: ' + a + '\t' + b);

    var result = 0;
    if(a > b)
        result = 1;
    if(a < b)
        result = -1;

    console.log('result : ' + result);
    return result;
};

source.sort(sortby);

/*
 *    输出日志及分析如下:
 *    
 *    ["A1", "A9", "A0", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A1    A9
 *    result : -1
 *    ["A1", "A9", "A0", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第一步,比较[0][1]两个元素并排序,看起来像是冒泡排序。
 *    -----------------------------------------------------------
 *    compare: A9    A0
 *    result : 1
 *    ["A1", "A9", "A9", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第二步,比较[1][2]两个元素并排序。
 *    疑①:结果有些奇怪,按照冒泡排序的话理应将[1][2]两个元素调换位置变成[2][1],
 *         但这里确是[1][1],感觉应该是将[2]保存到临时变量中了,然后将[1]赋值给了[2],
 *         所以,这里应该是一个中间状态,这一步操作没有完成。
 *    -----------------------------------------------------------
 *    compare: A1    A0
 *    result : 1
 *    ["A0", "A1", "A9", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第三步,按照上面的冒泡推断,将临时变量中的[2]赋值给了[1]。
 *    疑②:这一步与上一步应该可以一步完成,不知道为什么用了两步。
 *    -----------------------------------------------------------
 *    compare: A9    A5
 *    result : 1
 *    ["A0", "A1", "A9", "A9", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第四步,比较[2][3]两个元素并排序。
 *    疑③:同①,产生了相同元素,并将[3]保存到临时变量中。
 *    -----------------------------------------------------------
 *    compare: A1    A5
 *    result : -1
 *    ["A0", "A1", "A5", "A9", "A3", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第五步,比较[2][3]两个元素并排序,初步断定为冒泡排序,因为疑点的存在,可能为变种。
 *    疑④:同②,利用两步完成了冒泡排序中的一步。
 *    -----------------------------------------------------------
 *    compare: A9    A3
 *    result : 1
 *    ["A0", "A1", "A5", "A9", "A9", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第六步,比较[3][4]两个元素并排序。
 *    疑⑤:同③,产生了相同元素,并将[4]保存到临时变量中。
 *    -----------------------------------------------------------
 *    compare: A5    A3
 *    result : 1
 *    ["A0", "A1", "A5", "A5", "A9", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第七步,比较[2]与临时变量中的[4],并将[2]存入临时变量中并将[2][3]都变成了[2]。
 *    疑⑥:按照冒泡排序,应该直接调换[3][4]两个元素的位置就好了(即使上面用了两步完成这个调换操作),
 *         但是这里将临时变量中的[4]与不相关的[2]做比较就有些奇怪了
 *    -----------------------------------------------------------
 *    compare: A1    A3
 *    result : -1
 *    ["A0", "A1", "A3", "A5", "A9", "A2", "A7", "A8", "A4", "A6"]
 *    分析:第八步,至此到[4]之前都已经排序完成,虽然上面异步操作有点奇怪。
 *    -----------------------------------------------------------
 *    compare: A9    A2
 *    result : 1
 *    ["A0", "A1", "A3", "A5", "A9", "A9", "A7", "A8", "A4", "A6"]
 *    分析:第九步,比较[4][5]两个元素,产生了相同元素,并将[5]保存到临时变量中,一直在重复这个奇怪的操作。
 *    -----------------------------------------------------------
 *    compare: A5    A2
 *    result : 1
 *    ["A0", "A1", "A3", "A5", "A5", "A9", "A7", "A8", "A4", "A6"]
 *    分析:第十步,比较[3]和临时变量中的[5]。这就有意思了,为什么要去跟[3]比较呢?[3]有什么特殊的地方吗?
 *         确实,仔细看我们就会发现[0][1][2][3][4]现在都是有序的,而[3]正好处于中间位置,
 *         这让我们不由得联想到二分法,再结合上面的第七步,果然也符合这个推断,确实是使用了二分法。
 *         这也解释了为什么在一至六步中会使用两步来完成调换操作,其实并不是简单的调换,
 *         而是使用了一次二分法插入排序。
 *    -----------------------------------------------------------
 *    compare: A3    A2
 *    result : 1
 *    ["A0", "A1", "A3", "A3", "A5", "A9", "A7", "A8", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A1    A2
 *    result : -1
 *    ["A0", "A1", "A2", "A3", "A5", "A9", "A7", "A8", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A9    A7
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A9", "A9", "A8", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A5    A7
 *    result : -1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A9", "A8", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A9    A8
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A9", "A9", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A7    A8
 *    result : -1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A9", "A4", "A6"]
 *    -----------------------------------------------------------
 *    compare: A9    A4
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A9", "A9", "A6"]
 *    -----------------------------------------------------------
 *    compare: A8    A4
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A8", "A9", "A6"]
 *    -----------------------------------------------------------
 *    compare: A7    A4
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A7", "A7", "A8", "A9", "A6"]
 *    -----------------------------------------------------------
 *    compare: A5    A4
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A5", "A5", "A7", "A8", "A9", "A6"]
 *  -----------------------------------------------------------
 *    compare: A3    A4
 *    result : -1
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A9", "A6"]
 *    -----------------------------------------------------------
 *    compare: A9    A6
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A9", "A9"]
 *    -----------------------------------------------------------
 *    compare: A8    A6
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A8", "A9"]
 *    -----------------------------------------------------------
 *    compare: A7    A6
 *    result : 1
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A7", "A8", "A9"]
 *    -----------------------------------------------------------
 *    compare: A5    A6
 *    result : -1
 *    ["A0", "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"]
 *    
 */

经过上面的执行日志分析,我们发现:javascript中的.sort(sortby)方法使用的是一个冒泡排序的变种方式,当遇到需要调整顺序的相邻元素时,冒泡排序会直接调换两者的位置,但javascript中的.sort(sortby)方法,会将需要前移的元素使用二分法直接插入到正确的位置。

.sort() 方法深层探究[2]: 为什么返回 true/false 对长度为10以内的数组的排序结果不会造成影响

首先,咱们先来分析一下,为什么返回true/false在某些情况下对排序结果没有影响

根据.sort()函数定义

  • 若 a < b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值 (此时不需要调整顺序)。
  • 若 a == b,则返回 0 (此时不需要调整顺序)。
  • 若 a > b,则返回一个大于 0 的值 (此时需要调整顺序)。

我们可以看出来:只有a > b时,才需要对数组元素调整顺序,而a > b时若按照true/false的返回值来说,应该返回true,而true在javascript中,大家都知道,是等价于1的,是一个大于0的值。正好与函数的定义相匹配,这也说明了为什么在某些情况下,sortby函数即使返回true/false也不会影响排序结果的正确性。

OK,上面也说的,在某些情况下,那么到底在什么情况下呢?

根据我多次测试,在数组长度 <= 10 的情况下,无论返回 true/false 还是 1/0/-1 都不影响排序结果的正确性;而一旦数组长度超过10,排序结果就无法保证了。

为什么是10?

按理说,根据上面的算法分析,我们已经知道了.sort(sortby)函数的具体实现,本来我真的是打算研究一下这个问题的,可是,you know,对于一个算法学渣来说,这个问题还是太难了。。。(﹁"﹁)

权且记录一下,如果哪天我突然顿悟了,我会补回来的٩(ŏ﹏ŏ、)۶

还有,真的,如果哪位大神明白的,麻烦再评论里教我下,感激不尽。。。

✎﹏ 本文来自于 momo314和他们家的猫,文章原创,转载请注明作者并保留原文链接。