JavaScript中的Array.prototype.sort方法详解

Snailclimb 发布于2019-08-22 15:36 / 1424人阅读

摘要：方法可以接受一个可选的参数，比较回调函数。方法会修改原本数组输出如上，在调用方法后，自身数组被修改。对于长数组会使用快速排序，而快速排序一般是不稳定的。所以方法返回的数组永远是该方法认为的升序数组。

前几天在某公司面试的时候被问到关于这个方法的默认值的问题（然而面试官跟我说的其实是错的，当场我还不够底气去反驳）。突然发现对这个方法的了解还不够，因此回来查了资料，看了v8引擎的实现和ECMA标准，在这分享一下我的总结。

先给几个结论把，然后我们再从ECMA标准去看这个方法。

sort方法会修改原本数组。

sort方法是不稳定的。

sort方法可以接受一个可选的参数，comparefn(比较回调函数)。

sort方法始终是默认升序的。

1.sort方法会修改原本数组

let a = [1, 20, 13, 110]
a.sort()
console.log(a) // 输出[1, 110, 13, 20]

如上，a在调用sort方法后，自身数组被修改。

2.sort方法是不稳定的

这句话具体来说应该是，sort方法在长数组排序的时候是不稳定的。在v8引擎的里，对于短数组会使用插入排序，而插入排序是稳定的。对于长数组会使用快速排序，而快速排序一般是不稳定的。具体可以读v8引擎的代码，v8引擎内的数组方法实现,从710行开始。

3.sort方法可以接受一个可选的参数，ccomparefn(比较回调函数)。

我们来看一下v8引擎中关于这一部分的代码

  if (!IS_CALLABLE(comparefn)) {
    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);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
  }

可以看出，在不传递comparefn这个参数的情况下，默认会使用转换为的字符串的诸个字符的Unicode位点进行排序。另外值得注意的一点是，undefined在默认情况下总是会被排在数组的最后，这一点可以参考ECMA-262标准中关于Array.prototype.sort(comparefn)的描述。

When the SortCompare operatoris called with two arguments x and y, the
following steps are taken:

If x and y are both undefined, return +0.
If x is undefined, return 1.
If y is undefined, return −1.
If the argument comparefn was not provided in the call to sort, go to step 7.
Call comparefn with arguments x and y.
Return Result(5).
Call ToString(x).
Call ToString(y).
If Result(7) < Result(8), return −1.
If Result(7) > Result(8), return 1.
Return +0.

以下是我简单翻译的规则:

当比较操作函数用x,y两个参数调用的时候，会按照接下来的步骤进行：

如果x,y都是undefined，返回 +0

如果x是undefined,返回 1

如果y是undefined,返回 -1

如果没有提供comparefn，跳至第七步

用comparefn比较x,y

返回第五步的比较结果

x.toString()

y.toString()

如果第八步大于第七步，返回-1

如果第七步大于第八步，返回1

返回+0

因此[1, 20, 2, 10].sort()的结果会是[1, 10, 2, 20],而不是预期的[1, 2, 10, 20]。

4. sort方法始终是默认升序的。

另外关于如何根据x,y比较结果进行排序，有以下规则：

如果 comparefn(a, b) 小于 0 ，那么 a 会被排列到 b 之前；

如果 comparefn(a, b) 等于 0 ， a 和 b 的相对位置不变。备注： ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守（例如 Mozilla 在 2003 年之前的版本, 例如v8引擎，这一点其实就是上面所说的排序不稳定）；

如果 comparefn(a, b) 大于 0 ， b 会被排列到 a 之前。

所以sort方法返回的数组永远是该方法认为的升序数组。我们要做的事情就是令我们想要放在后面的数大于放在前面的数。

比如我们想要返回一个降序的数字数组传入的comparefn应该是 (a, b) => b - a

参考资料：

MDN关于sort算法的文档

v8引擎数组实现

ECMA-262标准

GPU云服务器云服务器方法参数详解方法签名详解 javascript详解 grep()方法详解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/93587.html

【JS必知必会】高阶函数详解与实战

摘要：函数作为参数情况，，和是中内置的高阶函数。知道了到底啊什么是高阶函数，有哪些类型的高阶函数。公众号技术栈路线大家好，我是，公众号程序员成长指北作者，这篇文章是必知必会系列的高阶函数讲解。前言一道经典面试题： //JS实现一个无限累加的add函数 add(1) //1 add(1)(2) //3 add(1)(2)(3) //6 当大家看到这个面试题的时候，能否在第一时间想到...

李昌杰 2019-08-26 10:12 评论0 收藏0
【深度长文】JavaScript数组所有API全解密

摘要：关于我的博客掘金专栏路易斯专栏原文链接深度长文数组全解密全文共字，系统讲解了数组的各种特性和。构造器构造器用于创建一个新的数组。中声明的数组，它的构造函数是中的对象。本文首发于CSDN网站，下面的版本又经过进一步的修订。关于我的博客：louis blog 掘金专栏：路易斯专栏原文链接：【深度长文】JavaScript数组全解密全文共13k+字，系统讲解了JavaScrip...

Mr_zhang 2019-08-20 16:13 评论0 收藏0
深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
Array.prototype.sort()方法到底是如何排序的？

摘要：本文除了会带大家了解一些方法后面简写为方法的基本定义和用法之外，还会探讨一下方法到底是使用的什么排序算法。下面我们来看看方法到底是如何排序的。本文除了会带大家了解一些Array.prototypr.sort()方法(后面简写为sort()方法)的基本定义和用法之外，还会探讨一下sort()方法到底是使用的什么排序算法。简单度娘了一下，网上的那些sort()方法详解文章，大多只说了...

youkede 2019-08-20 16:12 评论0 收藏0
JavaScript之数组

摘要：数组的特别之处在于，当使用小于的非负整数作为属性名时数组会自动维护其属性值。返回的数组包含第一个参数指定的位置和所有到但不含第二个参数指定的位置之间的所有数组元素。数组中只需有一项满足给定条件则返回。概念 JavaScript数组是JavaScript对象的特殊形式。数组索引实际上和碰巧是整数的属性名差不多，使用方括号访问数组元素就像用方括号访问对象的属性一样。JavaScript将...

coolpail 2019-08-23 18:33 评论0 收藏0