理解JavaScript中的sort()方法

阅读次数: 次 2020-07-29

字数：3.3k字 | 预计阅读时长：12分钟

editor-page-cover

初识`sort()`方法

先来看一下MDN上是如何定义的：

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。

这里有几点要注意：

对数组元素排序后，返回的数组是新数组吗？
默认排序会将元素转换为字符串，然后根据编码进行排序，这样会有什么问题？
排序大小顺序如何？
如何不使用默认排序？传入什么参数吗？
何为原地算法？

先提出这些问题，在正文中会进行解答。

`sort()`方法的语法

arr.sort([compareFunction])
/* 
	参数：
	compareFunction(可选)：用来指定某种顺序进行排列的函数。如果省略，元素按照转换为字符串的各个字符的
	Unicode码点进行排序。
	firstEl：第一个用于比较的元素
	secondEl：第二个用于比较的元素
	
	返回值：
	排序后的数组。数组已经原地排序，并且不进行复制。
*/

通过sort()方法的语法，我们可以大致知道几条信息了，并且能回答一开始的问题了。

Q：对数组排序后，返回的数组是新数组吗？

A：不是，数组进行原地排序，不进行复制，因此当一个数组执行了sort()方法以后，原数组就会发生变化。

Q：如何不使用默认排序？传入什么参数吗？

A：通过向sort()方法中传入compareFunction比较函数这个参数可以指定排序时的顺序。具体如何实现请接着往下看。

使用`sort`进行排序

在JavaScript中是没有规定数组中必须存放相同类型的元素的，即：你可以按照常规的做法，一个数组中都存在相同类型的值，比如都存放字符串，或者都存在对象，当然，你还可以用数组存放函数，甚至，你可以在一个数组中同时保存字符串、数值、对象等。

对字符串值进行排序

在定义中，我们可以从「默认排序顺序是将元素转换为字符串，然后通过它们的Unicode编码的位置进行排序」这句话中得到这样一个隐藏信息：数组中字符串类型的元素是按照Unicode编码来进行排序的。

来看一下常见的数字、大小写字母、汉字等的编码

它们的编码顺序大致如下：

数字 > 英语大写字母 > 英语小写字母 > 汉字

案例1

在数组中定义多个字符串元素，尝试对这个数组进行排序。我们来验证一下排序结果是否是按照unicode编码的顺序进行的。

代码如下：

1
2
3

var warning = ["不要吃蝙蝠", "don't eat the bat", "DON'T EAT THE BAT", '886'];
warning.sort();
console.log(warning);

输出结果为：

可以看到，最终的排序结果和字符在unicode编码中出现的位置是一致的。

数字被排在最前面，紧接着是大写字母，然后是小写字母，最后是汉字。

案例2

现在，我们对上面数组中的元素做一些更改，将字符串'886'更改为数值886，再进行一次排序。

1
2
3

var warning = ["不要吃蝙蝠", "don't eat the bat", "DON'T EAT THE BAT", 886];
warning.sort();
console.log(warning);

输出结果为：

可以看到，当把字符串'886'改变为数值886，然后进行排序后的结果和案例1的输出结果一致。

这是为何呢？

想一下定义：

默认排序是将元素转换为字符串，然后按照字符的unicode编码进行排序。886这个数值在排序时，将会被转换为字符串，因此和案例1其实是一致的。

对数值进行排序

案例1

我们来尝试一下对arr数组进行排序，这个数组中保存的都是Number类型的数值

1
2
3

var arr = [45, 21, 14, 10, 1]
arr.sort();
console.log(arr);

排序后的结果为：

可以看到，原数组arr按照从小到大的顺序进行排序。这是sort()方法排序时的默认顺序(从小到大)

案例2

上面代码中的数组中的元素顺序比较规律，我们将数组的顺序打乱再试一次

1
2
3

var arr = [4, 6, 1, 10, 7, 24];
arr.sort();
console.log(arr);

输出结果为：

😨排序后的结果既不是从小到大，也不是从大到小！这是怎么回事？

还记得刚才的那个886吗？它是一个数字，它在排序时被转换成了字符串，然后按照unicode编码的顺序和其他的值进行排序了。

那么这个案例中的排序结果是如何来的呢？

伪代码如下：

1 2	var arr = [4, 6, 1, 10, 7, 24]; // => var arr = ['4', '6', '1', '10', '7', '24'];

然后进行排序时，将会针对每个字符串中的字符进行比较。例如元素10和元素24比较时，从第一个数字开始比较，1在编码表中的位置比2大，因此10自然就排在24前面了。

显然，这样的排序结果并不是我们想要的，那么如何正确的对数字进行排序呢？

数字数组排序的原理

分清比较函数中的参数`a`和参数`b`

先来看以下代码：

var arr = [3, 15, 8, 29, 102, 22];

// 在sort()方法中传入了比较函数，并且在比较函数中有两个参数a和b
arr.sort(function (a, b) {
    console.log('排序：' + a + ',' + b);
})
console.log(arr);

输出结果为：

从输出的结果不难发现，在每次进行比较时，将会先从数组中取出两个元素，两两进行比较。结合代码中变量位置及输出结果，我们就可以发现：每次执行排序时，需要从数组中取出两个元素，a对应着后一个数组元素，b对应着前一个数组元素。

弄清这一点，很重要！

我是如何理解比较函数的逻辑的

我的疑惑

本人脑袋并不灵光，所以一个很简单的问题，看很久，还是看不懂。比如，下面这段话：

MDN上还给出了比较函数的格式：

function compare(a, b) {
  if (a < b ) {           // 按某种排序标准进行比较, a 小于 b
    return -1;
  }
  if (a > b ) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

以及简化的代码：

1
2
3

function compareNumbers(a, b) {
  return a - b;
}

让我很费解的是为什么比较函数小于0时，a就会被排列到b之前，而比较函数大于0时，a就会被排列到b之后。有人说，这是规定！可以我觉得这个规定不容易理解，如果是靠死记硬背的话，根本记不了多久，可能就记混了。也有人说，那这就需要看底层了，底层代码就是那么规定的！

可是它为什么要这么规定呢？网上没有人回答我这个问题

为什么a被排列到b前，比较函数就要小于0呢？

其实上面的这段话，我觉得还有一个很容易让人迷惑的地方。那就是它并没有指明，上面的这段话都是针对数组升序排序的，而是直接默认了。

我是如何解决这个疑惑的

那么我是如何理解比较函数的逻辑的呢？

先来问一个问题，如果一段程序代码出错的时候，需要你返回一个值，代表出错，你会返回一个什么值？

应该是这个值吧：

return -1

如果return出去的是一个负值，这通常代表着程序出错，异常退出。如果你能理解这一点，接下来就好办了。

先来定义一个数组：

1	var arr = [3, 15, 8, 29, 102, 22];

我们先从数组升序开始说起。数组排序，最重要的就是在判断出两个元素的大小之后，要让它们交换位置。

那如何告诉底层当前正在排序的这两个元素，需要交换位置呢？
我们可以通过return语句返回一个标志
那返回什么的标志呢？
如果当前的这两个元素的位置不合理（不满足升序或降序排序），我们可以返回一个标志着“不合理”的标志，对啦！就是返回一个负值！！！

我们以这样的思路来捊一下：

数组升序：

先从数组中取两个元素，两两比较，在比较函数中，a是数组中后一个元素，b是数组中前一个元素
如果按升序排序，a大于b的话，即数组中后一个元素大于前一个元素，那么当前位置合理，不需要交换位置，因此我们的比较函数需要返回一个正数。这正对应着MDN上的话：a（后一个元素）要被排列到b（后一个元素）之后时，比较函数大于0。
如果a小于b的话，即数组中后一个元素小于前一个元素，那么当前位置不合理，需要交换位置，因此我们的比较函数需要返回一个负数。这正对应着MDN上的话：a（后一个元素）要被排列在b（前一个元素）之前时，比较函数小于0。
如果a等于b的话，当前位置也是合理的，不需要交换位置，因此我们的比较函数可以返回一个0。

这时候再来看这段代码：

function compare(a, b) {
  if (a < b ) {  // 如果a(后一个元素)小于b(前一个元素)，即当前位置不满足从小到大的升序排列，返回负值
    return -1;
  }
  if (a > b ) { // 如果a(后一个元素)大于b(前一个元素)，即当前位置满足从小到大的升序排列，返回正值
    return 1;
  }
  // a must be equal to b
  return 0;
}

如果能理解这段代码了，自然也能理解简化的代码了：

后一个值大于前一个值，返回正值；后一个值小于前一个值，返回负值。因此，我们可以让后一个值减去前一个值，就能做到a > b时，a - b返回正值，a < b时，a - b返回负值，于是，就简化了代码。

1
2
3

function compareNumbers(a, b) {
  return a - b;
}

数组降序：

说完数组升序，再来说一下数组降序：

先从数组中取两个元素，两两比较，在比较函数中，a是数组中后一个元素，b是数组中前一个元素
如果按降序排序，a小于b，即数组中后一个元素小于前一个元素，正好满足降序，元素位置合理，不需要交换，因此我们需要比较函数返回一个正值。如果替MDN把降序的话写出来，就是：a（后一个元素）要被排列在b（后一个元素）之后时，比较函数大于0。（刚好相反）
如果按降序排序，a大于b，即数组中后一个元素大于前一个元素，不能满足降序，元素位置不合理，需要交换，因此我们需要比较函数返回一个负值。如果替MDN把降序的话写出来，就是：a（后一个元素）要被排列在b（后一个元素）之前时，比较函数小于0。（刚好相反）
如果a等于b的话，当前位置也是合理的，不需要交换位置，因此我们的比较函数可以返回一个0。

这时候再来看这段代码：

function compare(a, b) {
  if (a < b ) {  // 如果a(后一个元素)小于b(前一个元素)，即当前位置满足从大到小的降序排列，返回正值
    return 1;
  }
  if (a > b ) { // 如果a(后一个元素)大于b(前一个元素)，即当前位置不满足从大到小的降序排列，返回负值
    return -1;
  }
  // a must be equal to b
  return 0;
}

当然，简化的代码也应该可以理解了

后一个值小于前一个值，返回正值，后一个值大于前一个值，返回负值。因此，我们可以让前一个值减去后一个值（刚好相反），就可以做到a > b时，b - a返回负值，a < b时，b - a返回正值。

1
2
3

function compareNumbers(a, b) {
  return b - a;
}

sort()方法的底层排序算法

我们再来对代码进行一下修改：

var arr = [3, 15, 8, 29, 102, 22];

arr.sort(function (a, b) {
    console.log(a + ' - ' + b + ' = ' +(a - b));
})
console.log(arr);

这一次在比较函数中加上返回值：

var arr = [3, 15, 8, 29, 102, 22];

arr.sort(function (a, b) {
    console.log(a + ' - ' + b + ' = ' +(a - b));
    return a - b;
})
console.log(arr);