Javascript的sort()是如何工作的?

How does the following code sort this array to be in numerical order?

下面的代码如何将这个数组按数值排序?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

I know that if the result of the computation is...

我知道如果计算的结果是…

Less than 0: "a" is sorted to be a lower index than "b".
Zero: "a" and "b" are considered equal, and no sorting is performed.
Greater than 0: "b" is sorted to be a lower index than "a".

小于0:“a”被排序为比“b”低的索引。零:“a”和“b”被认为是相等的，并且不执行排序。大于0:“b”被排序为比“a”低的索引。

Is the array sort callback function called many times during the course of the sort?

数组排序回调函数在排序过程中被多次调用吗?

If so, I'd like to know which two numbers are passed into the function each time. I assumed it first took "25"(a) and "8"(b), followed by "7"(a) and "41"(b), so:

如果是的话，我想知道每次有两个数字被传递到函数中。我假设第一次是“25”(a)和“8”(b)，然后是“7”(a)和“41”(b)，所以:

25(a) - 8(b) = 17 (greater than zero, so sort "b" to be a lower index than "a"): 8, 25

25(a) - 8(b) = 17(大于0，因此将“b”排序为比“a”低的索引):8,25

7(a) - 41(b) = -34 (less than zero, so sort "a" to be a lower index than "b": 7, 41

7(a) - 41(b) = -34(小于0，所以将a排序为比b低的索引:7,41

How are the two sets of numbers then sorted in relation to one another?

这两组数字之间是如何排序的呢?

Please help a struggling newbie!

请帮助一个挣扎的新手!

5 个解决方案

#1

Is the array sort callback function called many times during the course of the sort?

数组排序回调函数在排序过程中被多次调用吗?

Yes

是的

If so, I'd like to know which two numbers are passed into the function each time

如果是这样的话，我想知道哪两个数字每次都被传递到函数中。

You could find out your self with:

你可以通过:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

EDIT

编辑

This is the output I've got:

这是我得到的输出:

25,8
25,7
8,7
25,41

#2

The JavaScript interpreter has some kind of sort algorithm implementation built into it. It calls the comparison function some number of times during the sorting operation. The number of times the comparison function gets called depends on the particular algorithm, the data to be sorted, and the order it is in prior to the sort.

JavaScript解释器内置了某种类型的算法实现。它在排序操作期间多次调用比较函数。调用比较函数的次数取决于特定的算法、要排序的数据以及排序之前的顺序。

Some sort algorithms perform poorly on already-sorted lists because it causes them to make far more comparisons than in the typical case. Others cope well with pre-sorted lists, but have other cases where they can be "tricked" into performing poorly.

有些排序算法在已经排序的列表上执行得很差，因为它导致它们进行比通常情况多得多的比较。有些人能很好地处理预先排序的列表，但也有些人会被“欺骗”而表现不佳。

There are many sorting algorithms in common use because no single algorithm is perfect for all purposes. The two most often used for generic sorting are Quicksort and merge sort. Quicksort is often the faster of the two, but merge sort has some nice properties that can make it a better overall choice. Merge sort is stable, while Quicksort is not. Both algorithms are parallelizable, but the way merge sort works makes a parallel implementation more efficient, all else being equal.

由于没有一种算法适用于所有的目的，所以在常用的算法中有许多分类算法。通用排序最常用的两种方法是快速排序和合并排序。快速排序通常是两者中速度最快的，但是归并排序有一些很好的属性，可以使它成为更好的整体选择。归并排序是稳定的，而快速排序则不是。这两种算法都是可并行化的，但是合并排序的工作方式使并行实现更高效，在其他条件相同的情况下。

Your particular JavaScript interpreter may use one of those algorithms or something else entirely. The ECMAScript standard does not specify which algorithm a conforming implementation must use. It even explicitly disavows the need for stability.

您的特定JavaScript解释器可以使用其中一个算法或其他完全的方法。ECMAScript标准没有指定符合要求的实现必须使用的算法。它甚至明确表示不需要稳定。

#3

Pairs of values are compared, one pair at a time. The pairs that are compared are an implementation detail--don't assume they will be the same on every browser. The callback can be anything (so you can sort strings or Roman numerals or anything else where you can come up with a function that returns 1,0,-1).

对值进行比较，每次一对。被比较的对是实现细节——不要假设它们在每个浏览器上都是相同的。回调可以是任何东西(因此，您可以对字符串或罗马数字进行排序，或者其他任何可以产生返回1,0,1的函数的东西)。

One thing to keep in mind with JavaScript's sort is that it is not guaranteed to be stable.

要记住的一点是，JavaScript的排序并不能保证它是稳定的。

#4

Is the array sort callback function called many times during the course of the sort?

数组排序回调函数在排序过程中被多次调用吗?

Yes, that's exactly it. The callback is used to compare pairs of elements in the array as necessary to determine what order they should be in. That implementation of the comparison function is not atypical when dealing with a numeric sort. Details in the spec or on some other more readable sites.

是的,这就是它。回调用于根据需要比较数组中的元素对，以确定它们的顺序。当处理数字排序时，比较函数的实现并不是不典型的。说明中的细节或其他可读性更好的网站。

#5

Is the array sort callback function called many times during the course of the sort?

数组排序回调函数在排序过程中被多次调用吗?

Since this is a comparison sort, given N items, the callback function should be invoked on average (N * Lg N) times for a fast sort like Quicksort. If the algorithm used is something like Bubble Sort, then the callback function will be invoked on average (N * N) times.

由于这是一个比较排序，给定N个条目，回调函数应该被平均调用(N * lgn)次，以便进行快速排序。如果所使用的算法类似于Bubble Sort，那么回调函数将被平均调用(N * N)次。

The minimum number of invocations for a comparison sort is (N-1) and that is only to detect an already sorted list (i.e. early out in Bubble Sort if no swaps occur).

比较排序的最小调用数是(N-1)，这仅用于检测已排序的列表(例如，如果没有交换发生，则在冒泡排序的早期)。