排序函数如何在 JavaScript 中与比较函数一起工作

How does sort function work in JavaScript, along with compare function

提问by Kraken

As already asked: how does sort function work in JavaScript, along with the comparefunction? If I have an array, and I do array.sort(compare)now it was written in the book that if the comparefunction returns a-b(two indices of the array) then it works based on the fact that whether the result is greater than 0, less than 0 or equal to 0. But, how exactly does it work? I could not work it out.

正如已经问过的那样： sort 函数如何在 JavaScript 中与compare函数一起工作？如果我有一个数组，我array.sort(compare)现在这样做，书中写道，如果compare函数返回a-b（数组的两个索引），那么它的工作原理是结果是大于 0、小于 0 还是等于0. 但是，它究竟是如何工作的？我无法解决。

回答by Flimzy

The "compare" function must take two arguments, often referred to as aand b. Then you make the compare function return 0, greater than 0, or less than 0, based on these values, aand b.

“比较”函数必须采用两个参数，通常称为a和b。然后根据这些值a和b使比较函数返回 0、大于 0 或小于 0 。

1. Return greater than 0 if ais greater than b
2. Return 0 if aequals b
3. Return less than 0 if ais less than b

1. 如果a大于b，则返回大于 0
2. 如果a等于b，则返回 0
3. 如果a小于b，则返回小于 0

With these three return values, and only two arguments, it is possible to write a compare function that can sort any type of input data type, or complex data structures.

有了这三个返回值和两个参数，就可以编写一个比较函数，它可以对任何类型的输入数据类型或复杂的数据结构进行排序。

Then, when you call sort(), with your custom compare function, the compare function is called on pairs in your to-be-sorted list, to determine the proper ordering.

然后，当您使用自定义比较函数调用 sort() 时，将在待排序列表中的对上调用比较函数，以确定正确的排序。

Lets walk through a simple example... Suppose you're only sorting some numbers, so we have a very simple compare function:

让我们来看一个简单的例子......假设你只对一些数字进行排序，所以我们有一个非常简单的比较函数：

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

Simply subtracting b from a will always return greater than zero if a is larger than b, 0 if they are equal, or less than zero if a is less than b. So it meets the requirements for a compare function.

如果 a 大于 b，则简单地从 a 中减去 b 将始终返回大于零，如果它们相等，则返回 0，如果 a 小于 b，则返回小于零。因此它满足比较功能的要求。

Now lets suppose this is our list of numbers to sort:

现在让我们假设这是我们要排序的数字列表：

var numbers = [1,5,3.14];

When you call numbers.sort(compare), internally it will actually execute:

当您调用 时numbers.sort(compare)，它会在内部实际执行：

compare(1,5);     // Returns -4, a is less than b
compare(1,3.14);  // Return -2.14, a is less than b
compare(5,3.14);  // returns 1.86, a is greater than b

If you've ever done manual sorting or alphabetizing, you've done precisely the same thing, probably without realizing it. Even though you may have dozens or hundreds of items to compare, you're constantly comparing only two numbers (or author's last names, or whatever) at a time. Going through or short list of three numbers again, you'd start by comparing the first two numbers:

如果您曾经进行过手动排序或按字母顺序排列，那么您已经完成了完全相同的事情，可能没有意识到这一点。即使您可能有数十或数百个项目要比较，但您一次只能比较两个数字（或作者的姓氏，或其他）。再次浏览或列出三个数字，您首先要比较前两个数字：

1. Is 1 greater than or less than 5? Less than, so put these two numbers in our list: 1,5
2. Is 3.14 greater than or less than 1? Greater than, so it goes after 1 in the new list
3. Is 3.14 greater than or less than 5 in our new list? Less than, so it goes before 5. Our new list is now [1,3.14,5]

1. 1是大于还是小于5？小于，所以把这两个数字放在我们的列表中：1,5
2. 3.14 是大于还是小于 1？大于，所以它在新列表中的 1 之后
3. 在我们的新列表中，3.14 是大于还是小于 5？小于，所以它在 5 之前。我们的新列表现在是 [1,3.14,5]

Because you can provide your own compare() function, it is possible to sort arbitrarily complex data, not just numbers.

因为您可以提供自己的 compare() 函数，所以可以对任意复杂的数据进行排序，而不仅仅是数字。

回答by nnnnnn

By default, the array sort()method sorts alphabetically ascending. If you want to sort in some other order, because your array contains numbers or objects then you can pass a function in to the sort().

默认情况下，数组sort()方法按字母升序排序。如果您想以其他顺序排序，因为您的数组包含数字或对象，那么您可以将一个函数传递给sort().

The function you pass in takes two parameters, often called a and b, and returns: a negative number if the first argument should be sorted before the second (a < b) 0 if the arguments are equal (a==b) a positive number if the first argument should be sorted after the second (a > b)

您传入的函数接受两个参数，通常称为 a 和 b，并返回： 如果第一个参数应该排在第二个之前，则为负数 (a < b) 0 如果参数相等 (a==b) 正数如果第一个参数应该在第二个 (a > b) 之后排序，则为 number

Now, here is the key bit: the function you pass as a parameter to sort()will be called repeatedly by sort()as it processes the whole array. sort()doesn't know or care about the datatype of the things in the array: each time it needs to know "Does item A come before item B?" it just calls your function. You don't need to worry about what type of sort algorithm is used internally by sort(), indeed one browser might use a different algorithm to another, but that's OK because you just have to provide a way for it to compare any two items from your array.

现在，这里是关键点：您作为参数传递给的函数sort()将在sort()处理整个数组时重复调用。sort()不知道或不关心数组中事物的数据类型：每次需要知道“项目 A 是否在项目 B 之前？” 它只是调用你的函数。您无需担心 内部使用哪种类型的排序算法sort()，实际上一个浏览器可能使用与另一个浏览器不同的算法，但这没关系，因为您只需要提供一种方法来比较数组中的任意两个项目.

Your function could have an if / else if / elsestructure to decide what result to return, but for numbers simply returning (a-b) will achieve this for you because the result of the subtraction will be -ve, 0 or +ve and correctly put the numbers in ascending order. Returning (b-a) would put them descending:

您的函数可以有一个if / else if / else结构来决定返回什么结果，但对于数字，简单地返回 (ab) 将为您实现这一点，因为减法的结果将是 -ve、0 或 +ve，并且正确地将数字按升序排列。返回 (ba) 会使它们降序：

  var sortedArray = myArray.sort(function(a,b){
                                    return (a-b);
                                });

If you had an array of objects and wanted to sort on some particular property or properties of the objects you could do that too. Assuming, e.g., objects in this format:

如果您有一个对象数组并且想要对对象的某个或多个特定属性进行排序，您也可以这样做。假设，例如，这种格式的对象：

{ id : 1,
  name : "Fred",
  address : "12 Smith St",
  phone : "0262626262" }

Then you could sort an array of such objects by their 'id' attribute as follows:

然后，您可以按其 'id' 属性对此类对象的数组进行排序，如下所示：

var sortedArray = myArray.sort(function(a,b){
                                  return (a.id - b.id);
                              });

Or you could sort an array of such objects by their 'name' attribute (alphabetical) as follows:

或者，您可以按“名称”属性（字母顺序）对此类对象的数组进行排序，如下所示：

var sortedArray = myArray.sort(function(a,b){
                                   if (a.name < b.name)
                                      return -1;
                                   else if (a.name == b.name)
                                      return 0;
                                   else
                                      return 1;
                               });

Note that in my final example I've put the full if / else if / elsestructure I mentioned earlier.

请注意，在我的最后一个示例中，我已经放置了if / else if / else之前提到的完整结构。

For the example where you are sorting objects with multiple properties you could expand that further to include a secondary sort, that is, (in my example) if the name properties are equal you could then return a comparison of, say, the phone property.

对于您对具有多个属性的对象进行排序的示例，您可以进一步扩展它以包括二级排序，也就是说，（在我的示例中）如果名称属性相等，那么您可以返回一个比较，例如，电话属性。

回答by gamgam

This method uses the syntax and parameters of the order of Array.sort (the compareFunction the sortOptions), whose parameters are defined as follows:

该方法使用了Array.sort(compareFunction sortOptions)的语法和参数，其参数定义如下：

compareFunction - a comparison function used to determine the sort order of the array elements. This parameter is optional. The comparison function should be used to compare the two parameters. A and B of a given element, the result of compareFunction can have a negative value, 0 or a positive value:

compareFunction - 一个比较函数，用于确定数组元素的排序顺序。该参数是可选的。应该使用比较函数来比较两个参数。给定元素的 A 和 B，compareFunction 的结果可以是负值、0 或正值：

If the return value is negative, it means that A appears before B in the sorted sequence. If the return value is 0, then A and B have the same sort order. If the return value is positive, it means that A appears after B in the sorted sequence.

如果返回值为负，则表示在排序序列中 A 出现在 B 之前。如果返回值为 0，则 A 和 B 具有相同的排序顺序。如果返回值为正，则表示在排序序列中 A 出现在 B 之后。

回答by Eiko No Shance

sort method alone treat numbers as strings so if the array of strings you don't need the compare function. but if the array of numbers you need the compare function to alter the build behavior of the sort method.

sort 方法单独将数字视为字符串，因此如果字符串数组不需要比较函数。但是如果数字数组需要比较函数来改变排序方法的构建行为。

ex1 :strings

ex1：字符串

var animals = ["Horse", "Cat", "Tiger", "Lion"];  
animals.sort();

ex2 : numbers

ex2 : 数字

var marks = [70, 90, 60, 80 ];  
marks.sort(function(a, b){return a > b}); //ascending , a < b descending . 

回答by Nicolas Mellado

You can use Uint32Array at the moment to create the array.

您现在可以使用 Uint32Array 来创建数组。

[https://i.stack.imgur.com/qBgvm.png]

[ https://i.stack.imgur.com/qBgvm.png]

but, it has some difficulties. For example, you can't add a new value to the array. Simply, you can't modify the array length.

但是，它有一些困难。例如，您不能向数组添加新值。简单地说，您不能修改数组长度。

回答by alexyangfox

I think it may be like this(well, I am not sure about this.)：

我想可能是这样的（好吧，我不确定这个。）：

suppose the function compare(a,b)is the compare function. It returns c. suppose we are going to sort the entries in the arrayNto get the sort result array M.

假设函数compare(a,b)是比较函数。它返回 c。假设我们要对数组中的条目进行排序N以获得排序结果数组M。

I don't know the exact sort algorithm , and different browsers even return different results if cis neither (a-b)nor (b-a)(say, if cis "b-2", "a+b"or some other expressions).

我不知道确切的排序算法，如果不同的浏览器甚至返回不同的结果c既不是(a-b)也不是(b-a)（说，如果 c是"b-2"，"a+b"或者一些其他表达式）。

But according to ECMA-262, the sort result should be like this:

但根据ECMA-262，排序结果应该是这样的：

a , b can be any two of the indexes. this means we actually passed an ordered pair to the compare function. eg: (0,1),(1,4), or even (2,0) , (2,1).

a , b 可以是任意两个索引。这意味着我们实际上将一个有序对传递给了比较函数。 eg: (0,1),(1,4), or even (2,0) , (2,1).

The ECMAScript Language Specification says the result should have this property: (a,b)is an ordered pair passed to the compare function.

ECMAScript 语言规范说结果应该具有以下属性： (a,b)是传递给比较函数的有序对。

• if c(what the function returns) is less than zero, then M(a)< M(b)must be satisfied.

• 如果c（函数返回的）小于零，则M(a)< M(b)必须满足。

And the specification talks nothing about what would happen if c is zero or bigger than zero.

并且规范没有提到如果 c 为零或大于零会发生什么。

I am not sure whether this is right. At least this can easily explain why when cis "a-b", the entries are sorted to be numerically and ascending, and why when cis "b-a",the entries are sorted to the opposite.

我不确定这是否正确。至少这可以很容易地解释为什么 when cis "a-b"，条目按数字和升序排序，以及为什么 when cis "b-a"，条目排序相反。

Are the js engines of the browsers are not really designed strictly according to `ECMA-262 or am I totally wrong?

浏览器的 js 引擎是不是真的严格按照 ECMA-262 设计的，还是我完全错了？

Reference：

参考：

The Fifth Edition of ECMA-262 (Check page 129-130)

ECMA-262 第五版（查看第 129-130 页）