Array.prototype.sort（compareFn）在浏览器中的工作方式不同？ [英] Array.prototype.sort(compareFn) works different in browsers?

问题描述

当compareFn返回value = 0时，我一直在测试比较函数作为回调到 Array.prototype.sort（compareFn），但我得到了一个意外的Chrome中的行为：

I've been testing the compare function given as callback to the Array.prototype.sort(compareFn) when the compareFn returns value = 0, but i get a unexpected behaviour in Chrome:

/* Chrome */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;})
//WUT? returns [6, 1, 3, 4, 5, 2, 7, 8, 9, 10, 11]

/* Firefox */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;});
//Work's fine: returns [1,2,3,4,5,6,7,8,9,10,11]

有人知道发生了什么吗？

推荐答案

我在Chrome中遇到了意外行为。有人知道会发生什么吗？

I get unexpected behaviour in Chrome. Anybody know what happens?

实际上，这并不意外。您的Firefox浏览器版本似乎实现了稳定的排序，而您的Chrome浏览器版本却没有。浏览器不需要采用稳定的排序算法（并且可以选择性能而不是稳定性）。

Actually, this is not unexpected. It appears that your Firefox browser version implements stable sorting, whereas your Chrome browser version does not. Browsers are not required to adopt a stable sorting algorithm (and may choose performance over stability).

稳定的排序算法返回相同的列表项，其顺序与它们最初出现的顺序相同而不稳定的排序算法则没有。

A stable sorting algorithm returns equal list items in the same order as they appear originally, whereas an unstable sorting algorithm does not.

考虑以下示例，其中a 11名男子名单按年龄分类。排序算法看到9名同龄（45岁），1名年龄（39岁）和一名年龄（52岁）的男性。排序后，最年轻的一个（迈克）首先出现在列表中，然后相同年龄的9个可以按任何顺序出现，然后是最后一个（利亚姆）。

Consider the following example, where a list of 11 men is sorted according to their age. The sorting algorithm sees 9 men of the same age (45 years old), one younger (39 years old), and one older (52 years old). After sorting, the youngest one (Mike) appears first in the list, then the 9 of the same age may appear in any order, and then the oldest one (Liam) at the end.

console.log([
    {name: 'John', age: 45},
    {name: 'Pete', age: 45},
    {name: 'Matt', age: 45},
    {name: 'Liam', age: 52},
    {name: 'Jack', age: 45},
    {name: 'Will', age: 45},
    {name: 'Zach', age: 45},
    {name: 'Josh', age: 45},
    {name: 'Ryan', age: 45},
    {name: 'Mike', age: 39},
    {name: 'Luke', age: 45}
  ].sort(function(a, b){
    // sort by ascending age
    return a.age - b.age;
  }).map(function(i){
    // get a sorted list of names
    return i.name;
  }).join(', ')
);

当我在Chrome中运行时，我得到

When I run this in Chrome, I get

Mike, Will, Matt, John, Jack, Pete, Zach, Josh, Ryan, Luke, Liam

这显然代表了一种不稳定的类型。一个稳定的排序将会返回

which clearly represents an unstable sort. A stable sort would have returned

Mike, John, Pete, Matt, Jack, Will, Zach, Josh, Ryan, Luke, Liam

然而，对于排序算法，两个列表在表示年龄时是相同的，这就是排序algoritm被告知：

However, to a sorting algorithm, both lists are identical when representing age, which is what the sorting algoritm was told to:

39, 45, 45, 45, 45, 45, 45, 45, 45, 45, 52

浏览器差异

在您的代码示例中，您告诉排序算法所有列表项是相等的（通过从比较函数返回 0 ）。然后，不稳定的排序算法可以按任何顺序对这些项目进行排序（就像Chrome在列表中有11个项目时所做的那样），而稳定的排序算法将按原始顺序对相同的项目进行排序（如Firefox所做的那样）。

Browser differences

In your code example, you tell the sorting algorithm that all list items are equal (by returning 0 from the comparison function). An unstable sorting algorithm may then sort these items in any order (as Chrome does when there are 11 items in the list), whereas a stable sorting algorithm will sort equal items in original order (as Firefox does).

在您的Chrome排序示例中，包含10个项目的数组（似乎使用稳定算法排序）和包含11个项目的数组之间存在差异。 众所周知 Chrome使用了插入排序（稳定）对于较小的数组（< = 10项）和较大数组的Quicksort变种（不稳定）。

In your example of sorting in Chrome, there is a difference between the array with 10 items (which appears to be sorted with a stable algorithm) and the array with 11 items. It is known that Chrome uses Insertion sort (stable) for small arrays (<= 10 items), and a Quicksort variant (unstable) for larger arrays.

有关排序算法如何工作和排序稳定性的更多信息，请检查关于排序算法的维基百科，此前的SO问题或此页面包含各种排序算法的动画插图。

For more info on how sorting algorithms works and sorting stability, check out Wikipedia on sorting algorithms, this previous SO question or this page with animated illustrations of various sorting algorithms.

这篇关于Array.prototype.sort（compareFn）在浏览器中的工作方式不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！