blocks|key|327160|text|在排序过程中是否多次调用数组排序回调函数？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|327161|是的，就是这样。该回调用于根据需要比较数组中的元素对，以确定它们的顺序。在处理数值排序时，比较函数的实现并不是不常见的。详情请访问the+spec或some其他more+readable站点。|offset|length|327162|entityMap|0|LINK|mutability|MUTABLE|url|http://www.ecma-international.org/publications/standards/Ecma-262.htm|1|http://www.w3schools.com/jsref/jsref_sort.asp|2|https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort^0|0|1T|8|0|22|4|1|28|D|2|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]|$D|W|E|X|1|Y]|$D|Z|E|10|1|11]]|A|$]]|$1|F|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]|N|$5|I|J|K|A|$L|O]]|P|$5|I|J|K|A|$L|Q]]]]

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 <a href="http://www.ecma-international.org/publications/standards/Ecma-262.htm" rel="noreferrer">the spec</a> or on <a href="http://www.w3schools.com/jsref/jsref_sort.asp" rel="noreferrer">some</a> other <a href="https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort" rel="noreferrer">more readable</a> sites.

blocks|key|328742|text|JavaScript解释器中内置了某种sort+algorithm实现。在排序操作期间，它会多次调用比较函数。调用比较函数的次数取决于特定的算法、要排序的数据以及它在排序之前的顺序。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|328743|一些排序算法在已经排序的列表上表现不佳，因为这会导致它们进行比典型情况多得多的比较。其他人可以很好地处理预先排序的列表，但在其他情况下，他们可能会被“欺骗”而表现不佳。|328744|有许多常用的排序算法，因为没有一种算法是所有用途的完美算法。最常用于泛型排序的两个是Quicksort和merge+sort。快速排序通常是两种排序中较快的一种，但合并排序有一些很好的属性，可以使其成为更好的整体选择。合并排序是stable，而快速排序不是。这两种算法都是可并行化的，但合并排序的工作方式使并行实现更有效率，其他条件相同。|328745|您的特定JavaScript解释器可能会使用这些算法中的一种，或者完全使用其他算法。符合标准的实现必须使用ECMAScript标准does+not+specify+which+algorithm。它甚至明确地否认了稳定的必要性。|328746|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Sort_algorithm|1|http://en.wikipedia.org/wiki/Quicksort|2|http://en.wikipedia.org/wiki/Merge_sort|3|https://en.wikipedia.org/wiki/Stable_sort#Stability|4|http://www.ecma-international.org/publications/standards/Ecma-262.htm|5|http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11^0|J|E|0|0|0|16|9|1|1G|A|2|36|6|3|0|1H|A|4|1T|W|5|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@$A|12|B|13|1|14]]|C|$]]|$1|D|3|E|5|6|7|15|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|16|8|@]|9|@$A|17|B|18|1|19]|$A|1A|B|1B|1|1C]|$A|1D|B|1E|1|1F]]|C|$]]|$1|H|3|I|5|6|7|1G|8|@]|9|@$A|1H|B|1I|1|1J]|$A|1K|B|1L|1|1M]]|C|$]]|$1|J|3|-4|5|6|7|1N|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]|R|$5|M|N|O|C|$P|S]]|T|$5|M|N|O|C|$P|U]]|V|$5|M|N|O|C|$P|W]]|X|$5|M|N|O|C|$P|Y]]|Z|$5|M|N|O|C|$P|10]]]]

The JavaScript interpreter has some kind of <a href="http://en.wikipedia.org/wiki/Sort_algorithm" rel="noreferrer">sort algorithm</a> 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.

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 <a href="http://en.wikipedia.org/wiki/Quicksort" rel="noreferrer">Quicksort</a> and <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">merge sort</a>. 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 <a href="https://en.wikipedia.org/wiki/Stable_sort#Stability" rel="noreferrer">stable</a>, 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 <a href="http://www.ecma-international.org/publications/standards/Ecma-262.htm" rel="noreferrer">ECMAScript</a> standard <a href="http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11" rel="noreferrer">does not specify which algorithm</a> a conforming implementation must use. It even explicitly disavows the need for stability.

blocks|key|3086542|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3086543|在排序过程中，数组排序回调函数是否被多次调用？|blockquote|3086544|3086545|3086546|是|3086547|3086548|如果是这样，我想知道每次传递给函数的是哪两个数字|3086549|3086550|3086551|你可以通过以下方式找到你自己：|3086552|array.sort((a,b)+=>+{
++console.log(`comparing+${a},${b}`);
++return+a+>+b+?+1
+++++++++++++++:+a+===+b+?+0+
+++++++++++++++++++++++++:+-1;
});|code-block|syntax|javascript|3086553|编辑|offset|length|style|BOLD|3086554|这是我得到的输出：|3086555|25,8
25,7
8,7
25,41|3086556|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|2|0|0|0^^$0|@$1|2|3|-4|4|5|6|15|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|16|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|17|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|18|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|19|7|@]|8|@]|9|$]]|$1|H|3|-4|4|5|6|1A|7|@]|8|@]|9|$]]|$1|I|3|J|4|C|6|1B|7|@]|8|@]|9|$]]|$1|K|3|-4|4|5|6|1C|7|@]|8|@]|9|$]]|$1|L|3|-4|4|5|6|1D|7|@]|8|@]|9|$]]|$1|M|3|N|4|5|6|1E|7|@]|8|@]|9|$]]|$1|O|3|P|4|Q|6|1F|7|@]|8|@]|9|$R|S]]|$1|T|3|U|4|5|6|1G|7|@$V|1H|W|1I|X|Y]]|8|@]|9|$]]|$1|Z|3|10|4|5|6|1J|7|@]|8|@]|9|$]]|$1|11|3|12|4|Q|6|1K|7|@]|8|@]|9|$R|S]]|$1|13|3|-4|4|5|6|1L|7|@]|8|@]|9|$]]]|14|$]]

<blockquote>
 Is the array sort callback function called many times during the course of the sort?
</blockquote>

Yes

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

You could find out your self with:

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

EDIT

This is the output I've got:

<pre><code>25,8
25,7
8,7
25,41
</code></pre>

blocks|key|328795|text|比较成对的值，一次比较一对。所比较的对是实现细节--不要假设它们在每个浏览器上都是相同的。回调可以是任何东西(因此您可以对字符串或罗马数字进行排序，或者其他任何可以得到返回1,0，-1的函数的东西)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|328796|关于JavaScript的排序，需要记住的一件事是它不能保证是稳定的。|328797|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

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).

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

blocks|key|332029|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332030|在排序过程中，数组排序回调函数是否被多次调用？|blockquote|332031|332032|332033|由于这是一个比较排序，给定N个项，回调函数应该平均(N+*+Lg+N)次被调用，以便进行像Quicksort这样的快速排序。如果使用的算法类似于Bubble+Sort，那么回调函数将平均(N+*+N)次被调用。|offset|length|332034|比较排序的最小调用次数是(N-1)，这只是为了检测已经排序的列表(即，如果没有发生交换，则在冒泡排序中处于早期状态)。|332035|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Quicksort|1|http://en.wikipedia.org/wiki/Bubble_sort^0|0|0|0|0|19|9|0|20|B|1|0|0^^$0|@$1|2|3|-4|4|5|6|V|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|W|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|X|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|Y|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|Z|7|@]|8|@$H|10|I|11|1|12]|$H|13|I|14|1|15]]|9|$]]|$1|J|3|K|4|5|6|16|7|@]|8|@]|9|$]]|$1|L|3|-4|4|5|6|17|7|@]|8|@]|9|$]]]|M|$N|$4|O|P|Q|9|$R|S]]|T|$4|O|P|Q|9|$R|U]]]]

<blockquote>
 Is the array sort callback function called many times during the course of the sort?
</blockquote>

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 <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">Quicksort</a>. If the algorithm used is something like <a href="http://en.wikipedia.org/wiki/Bubble_sort" rel="nofollow noreferrer">Bubble Sort</a>, then the callback function will be invoked on average (N * N) times.

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).

blocks|key|3086720|text|var+array=[25,+8,+7,+41]

array.sort(function(a,b){
++console.log(`a+=+${a}+,+b+=+${b}`);
++return+a+-+b
});|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|3086721|输出|unstyled|3086722|3086723|a+=8，b=+25|unordered-list-item|3086724|a+=7，b=+8|3086725|a+=+41，b=+7|3086726|a+=+41，b=8|3086727|<代码>H110a=+41，b=25<代码>H211<代码>F212|3086728|在我的浏览器中(Google+Chrome版本70.0.3538.77+(官方版本)(64位))在第一次迭代中，参数a是数组中的第二个元素，参数b是数组的第一个元素。|offset|length|style|BOLD|3086729|如果比较函数返回|3086730|3086731|大于b的负值被前移到a。|ordered-list-item|3086732|大于a的正值被前移到b。|3086733|0(零)a和b都将保持原样。|3086734|3086735|entityMap^0|0|0|0|0|0|0|0|0|1M|B|20|A|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1B|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|1C|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|1D|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|1E|8|@]|9|@]|A|$]]|$1|K|3|L|5|J|7|1F|8|@]|9|@]|A|$]]|$1|M|3|N|5|J|7|1G|8|@]|9|@]|A|$]]|$1|O|3|P|5|J|7|1H|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1I|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|1J|8|@$U|1K|V|1L|W|X]|$U|1M|V|1N|W|X]]|9|@]|A|$]]|$1|Y|3|Z|5|F|7|1O|8|@]|9|@]|A|$]]|$1|10|3|-4|5|F|7|1P|8|@]|9|@]|A|$]]|$1|11|3|12|5|13|7|1Q|8|@]|9|@]|A|$]]|$1|14|3|15|5|13|7|1R|8|@]|9|@]|A|$]]|$1|16|3|17|5|13|7|1S|8|@]|9|@]|A|$]]|$1|18|3|-4|5|F|7|1T|8|@]|9|@]|A|$]]|$1|19|3|-4|5|F|7|1U|8|@]|9|@]|A|$]]]|1A|$]]

<pre><code>var array=[25, 8, 7, 41]

array.sort(function(a,b){
 console.log(`a = ${a} , b = ${b}`);
 return a - b
});
</code></pre>

OUTPUT

<ul>
<li>a = 8 , b = 25</li>
<li>a = 7 , b = 8</li>
<li>a = 41 , b = 7</li>
<li>a = 41 , b = 8</li>
<li>a = 41 , b = 25</li>
</ul>

in my Browser (Google Chrome Version 70.0.3538.77 (Official Build) (64-bit) ) in the first iteration, the argument a is the Second element in an array and argument b is the First element of an array.

if the Compare function returns

<ol>
<li>Negative Value than b is moved forward to a.</li>
<li>positive Value than a is moved forward to b. </li>
<li>0(Zero) both a &amp; b will remain as it is.</li>
</ol>

blocks|key|328823|text|运行此代码。您可以看到从头到尾精确的一步一步的排序过程。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|328824|var+array=[25,+8,+7,+41]
var+count+=+1;
array.sort(+(a,b)+=>+{+
console.log(`${count%2B%2B}).+a:+${a}+%7C+b:+${b}`);
return+a-b;
});
console.log(array);|code-block|syntax|javascript|328825|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

run this code. You can see the exact step by step sorting process from the beginning to the end.

<pre><code>var array=[25, 8, 7, 41]
var count = 1;
array.sort( (a,b) =&gt; { 
console.log(`${count++}). a: ${a} | b: ${b}`);
return a-b;
});
console.log(array);
</code></pre>

blocks|key|3299939|text|Deeply+|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|3299940|如果结果为负，则将a排在b之前。|3299941|如果结果是肯定的，则b在a之前排序。|3299942|如果结果为0，则不会更改这两个值的排序顺序。|3299943|备注：|3299944|此代码是sort方法step+by+step内部的视图。|3299945|输出：|3299946|​|3299947|let+arr+=+[90,+1,+20,+14,+3,+55];
var+sortRes+=+[];
var+copy+=+arr.slice();		//create+duplicate+array
var+inc+=+0;	//inc+meant+increment
copy.sort((a,+b)+=>+{
	sortRes[inc]+=+[+a,+b,+a-b+];
	inc+%2B=+1;
	return+a+-+b;
});
var+p+=+0;
for+(var+i+=+0;+i+<+inc;+i%2B%2B)+{
	copy+=+arr.slice();
	copy.sort((a,+b)+=>+{
		p+%2B=+1;
		if+(p+<=+i+)+{
			return+a+-+b;
		}
		else{
			return+false;
		}
	});
	p+=+0;
	console.log(copy+%2B'+\t+a:+'%2B+sortRes[i][0]+%2B'+\tb:+'%2B+sortRes[i][1]+%2B'\tTotal:+'%2B+sortRes[i][2]);
}|code-block|syntax|javascript|3299948|3299949|entityMap^0|0|7|0|0|0|0|0|3|0|4|4|A|I|0|0|3|0|0|0|0^^$0|@$1|2|3|4|5|6|7|11|8|@$9|12|A|13|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|14|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|15|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|16|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|17|8|@$9|18|A|19|B|C]]|D|@]|E|$]]|$1|N|3|O|5|6|7|1A|8|@$9|1B|A|1C|B|C]|$9|1D|A|1E|B|C]]|D|@]|E|$]]|$1|P|3|Q|5|6|7|1F|8|@$9|1G|A|1H|B|C]]|D|@]|E|$]]|$1|R|3|S|5|6|7|1I|8|@]|D|@]|E|$]]|$1|T|3|U|5|V|7|1J|8|@]|D|@]|E|$W|X]]|$1|Y|3|S|5|6|7|1K|8|@]|D|@]|E|$]]|$1|Z|3|-4|5|6|7|1L|8|@]|D|@]|E|$]]]|10|$]]

Deeply Knowledge

If the result is negative a is sorted before b.

If the result is positive b is sorted before a.

If the result is 0 no changes are done with the sort order of the two values.

NOTE:

This code is the view inside of the sort method step by step.

OUTPUT:

<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) =&gt; {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i &lt; inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) =&gt; {
		p += 1;
		if (p &lt;= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}</code></pre>
</div>
</div>

blocks|key|3086949|text|为了帮助阐明Array#sort及其比较器的行为，请考虑在入门编程课程中教授的这个幼稚的insertion+sort：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3086950|​|3086951|const+sort+=+arr+=>+{
++for+(let+i+=+1;+i+<+arr.length;+i%2B%2B)+{
++++for+(let+j+=+i;+j+&&+arr[j-1]+>+arr[j];+j--)+{
++++++[arr[j],+arr[j-1]]+=+[arr[j-1],+arr[j]];
++++}
++}
};

const+array+=+[3,+0,+4,+5,+2,+2,+2,+1,+2,+2,+0];
sort(array);
console.log(""+%2B+array);|code-block|syntax|javascript|3086952|3086953|忽略选择插入排序作为算法，重点关注hardcoded比较器：arr[j-1]+>+arr[j]。这有两个与讨论相关的问题：|3086954|3086955|+>运算符是在成对的数组元素上调用的，但是您可能想要排序的许多东西，如对象，不能以合理的方式响应>+(如果您使用-).|ordered-list-item|3086956|Even处理数字，情况也是如此，通常您需要一些其他的排列方式，而不是这里已经烘焙的升序排序。|3086957|3086958|我们可以通过添加您熟悉的comparefn参数来解决这些问题：|3086959|3086960|const+sort+=+(arr,+comparefn)+=>+{
++for+(let+i+=+1;+i+<+arr.length;+i%2B%2B)+{
++++for+(let+j+=+i;+j+&&+comparefn(arr[j-1],+arr[j])+>+0;+j--)+{
++++++[arr[j],+arr[j-1]]+=+[arr[j-1],+arr[j]];
++++}
++}
};

const+array+=+[3,+0,+4,+5,+2,+2,+2,+1,+2,+2,+0];
sort(array,+(a,+b)+=>+a+-+b);
console.log(""+%2B+array);

sort(array,+(a,+b)+=>+b+-+a);
console.log(""+%2B+array);

const+objArray+=+[{id:+"c"},+{id:+"a"},+{id:+"d"},+{id:+"b"}];
sort(objArray,+(a,+b)+=>+a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray,+null,+2));|3086961|3086962|现在，简单的排序例程被推广了。您可以确切地看到何时调用此回调，回答您的第一组问题：|3086963|3086964|在排序过程中，数组排序回调函数是否被多次调用？如果是这样，我想知道每次传递给函数的是哪两个数字|blockquote|3086965|3086966|3086967|运行下面的代码可以看到，该函数被调用了很多次，您可以使用console.log查看传入了哪些数字：|3086968|3086969|const+sort+=+(arr,+comparefn)+=>+{
++for+(let+i+=+1;+i+<+arr.length;+i%2B%2B)+{
++++for+(let+j+=+i;+j+&&+comparefn(arr[j-1],+arr[j])+>+0;+j--)+{
++++++[arr[j],+arr[j-1]]+=+[arr[j-1],+arr[j]];
++++}
++}
};

console.log("on+our+version:");
const+array+=+[3,+0,+4,+5];
sort(array,+(a,+b)+=>+console.log(a,+b)+%7C%7C+(a+-+b));
console.log(""+%2B+array);

console.log("on+the+builtin:");
console.log(""+%2B+
++[3,+0,+4,+5].sort((a,+b)+=>+console.log(a,+b)+%7C%7C+(a+-+b))
);|3086970|3086971|你会问：|3086972|3086973|这两组数字之间的关系是如何排序的？|3086974|3086975|3086976|准确地说，a和b不是数字的集合--它们是数组中的对象(在您的示例中，它们是数字)。|3086977|事实是，它们如何排序并不重要，因为它依赖于实现。如果我使用了与插入排序不同的排序算法，比较器可能会在不同的数字对上调用，但在排序调用结束时，JS程序员最关心的不变量是结果数组根据比较器排序，假设比较器返回符合您声明的约定的值(当a+<+b时<0，当a+===+b时0，当a+>+b时>0)。|3086978|在同样的意义上，只要不违反规范，我就可以自由更改排序的实现，ECMAScript的实现可以在language+specification的范围内自由选择排序实现，因此Array#sort可能会在不同的引擎上产生不同的比较器调用。人们不会在逻辑依赖于某些特定的比较序列的情况下编写代码(比较器也不应该首先产生副作用)。|3086979|例如，当数组大于某个预先计算的元素数时，V8引擎(在编写本文时)调用Timsort，并对较小的数组块使用binary+insertion+sort。然而，它过去使用的是quicksort，这是不稳定的，可能会给出不同的参数序列和对比较器的调用。|3086980|因为不同的排序实现使用不同的比较器函数的返回值，所以当比较器不遵守约定时，这可能会导致令人惊讶的行为。有关示例，请参阅this+thread。|3086981|entityMap|0|LINK|mutability|MUTABLE|url|https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/sort|1|https://en.wikipedia.org/wiki/Insertion_sort|2|https://en.wikipedia.org/wiki/Hard_coding|3|https://tc39.es/ecma262/#sec-array.prototype.sort|4|https://github.com/v8/v8/blob/84cf890532510abda7ad4a8895fc8ad58799f1d1/third_party/v8/builtins/array-sort.tq#L5|5|https://github.com/v8/v8/blob/84cf890532510abda7ad4a8895fc8ad58799f1d1/third_party/v8/builtins/array-sort.tq#L490|6|https://en.wikipedia.org/wiki/Quicksort|7|https://stackoverflow.com/questions/52671125/why-does-sorting-a-js-array-of-numbers-with-work^0|6|A|6|A|0|18|E|1|0|0|0|0|U|H|H|9|2|0|0|1|1|1C|1|1K|1|0|0|0|C|9|0|0|0|0|0|0|0|0|0|S|B|0|0|0|0|0|0|0|0|0|5|1|7|1|0|36|5|3G|7|3R|5|0|2B|A|1A|M|3|0|Y|7|4|1G|L|5|2C|9|6|0|1N|B|7|0^^$0|@$1|2|3|4|5|6|7|2J|8|@$9|2K|A|2L|B|C]]|D|@$9|2M|A|2N|1|2O]|$9|2P|A|2Q|1|2R]]|E|$]]|$1|F|3|G|5|6|7|2S|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|2T|8|@]|D|@]|E|$K|L]]|$1|M|3|G|5|6|7|2U|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|2V|8|@$9|2W|A|2X|B|C]]|D|@$9|2Y|A|2Z|1|30]]|E|$]]|$1|P|3|-4|5|6|7|31|8|@]|D|@]|E|$]]|$1|Q|3|R|5|S|7|32|8|@$9|33|A|34|B|C]|$9|35|A|36|B|C]|$9|37|A|38|B|C]]|D|@]|E|$]]|$1|T|3|U|5|S|7|39|8|@]|D|@]|E|$]]|$1|V|3|-4|5|6|7|3A|8|@]|D|@]|E|$]]|$1|W|3|X|5|6|7|3B|8|@$9|3C|A|3D|B|C]]|D|@]|E|$]]|$1|Y|3|G|5|6|7|3E|8|@]|D|@]|E|$]]|$1|Z|3|10|5|J|7|3F|8|@]|D|@]|E|$K|L]]|$1|11|3|G|5|6|7|3G|8|@]|D|@]|E|$]]|$1|12|3|13|5|6|7|3H|8|@]|D|@]|E|$]]|$1|14|3|-4|5|6|7|3I|8|@]|D|@]|E|$]]|$1|15|3|16|5|17|7|3J|8|@]|D|@]|E|$]]|$1|18|3|-4|5|6|7|3K|8|@]|D|@]|E|$]]|$1|19|3|-4|5|6|7|3L|8|@]|D|@]|E|$]]|$1|1A|3|1B|5|6|7|3M|8|@$9|3N|A|3O|B|C]]|D|@]|E|$]]|$1|1C|3|G|5|6|7|3P|8|@]|D|@]|E|$]]|$1|1D|3|1E|5|J|7|3Q|8|@]|D|@]|E|$K|L]]|$1|1F|3|G|5|6|7|3R|8|@]|D|@]|E|$]]|$1|1G|3|1H|5|6|7|3S|8|@]|D|@]|E|$]]|$1|1I|3|-4|5|6|7|3T|8|@]|D|@]|E|$]]|$1|1J|3|1K|5|17|7|3U|8|@]|D|@]|E|$]]|$1|1L|3|-4|5|6|7|3V|8|@]|D|@]|E|$]]|$1|1M|3|-4|5|6|7|3W|8|@]|D|@]|E|$]]|$1|1N|3|1O|5|6|7|3X|8|@$9|3Y|A|3Z|B|C]|$9|40|A|41|B|C]]|D|@]|E|$]]|$1|1P|3|1Q|5|6|7|42|8|@$9|43|A|44|B|C]|$9|45|A|46|B|C]|$9|47|A|48|B|C]]|D|@]|E|$]]|$1|1R|3|1S|5|6|7|49|8|@$9|4A|A|4B|B|C]]|D|@$9|4C|A|4D|1|4E]]|E|$]]|$1|1T|3|1U|5|6|7|4F|8|@]|D|@$9|4G|A|4H|1|4I]|$9|4J|A|4K|1|4L]|$9|4M|A|4N|1|4O]]|E|$]]|$1|1V|3|1W|5|6|7|4P|8|@]|D|@$9|4Q|A|4R|1|4S]]|E|$]]|$1|1X|3|-4|5|6|7|4T|8|@]|D|@]|E|$]]]|1Y|$1Z|$5|20|21|22|E|$23|24]]|25|$5|20|21|22|E|$23|26]]|27|$5|20|21|22|E|$23|28]]|29|$5|20|21|22|E|$23|2A]]|2B|$5|20|21|22|E|$23|2C]]|2D|$5|20|21|22|E|$23|2E]]|2F|$5|20|21|22|E|$23|2G]]|2H|$5|20|21|22|E|$23|2I]]]]

To help clarify the behavior of <a href="https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/sort" rel="nofollow noreferrer"><code>Array#sort</code></a> and its comparator, consider this naive <a href="https://en.wikipedia.org/wiki/Insertion_sort" rel="nofollow noreferrer">insertion sort</a> taught in beginning programming courses:
<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>const sort = arr =&gt; {
 for (let i = 1; i &lt; arr.length; i++) {
 for (let j = i; j &amp;&amp; arr[j-1] &gt; arr[j]; j--) {
 [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
 }
 }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);</code></pre>
</div>
</div>

Ignoring the choice of insertion sort as the algorithm, focus on the <a href="https://en.wikipedia.org/wiki/Hard_coding" rel="nofollow noreferrer">hardcoded</a> comparator: <code>arr[j-1] &gt; arr[j]</code>. This has two problems relevant to the discussion:
<ol>
<li>The <code>&gt;</code> operator is invoked on pairs of array elements but many things you might want to sort such as objects don't respond to <code>&gt;</code> in a reasonable way (the same would be true if we used <code>-</code>).</li>
<li>Even if you are working with numbers, oftentimes you want some other arrangement than the ascending sort that's been baked-in here.</li>
</ol>
We can fix these problems by adding a <code>comparefn</code> argument which you're familiar with:
<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>const sort = (arr, comparefn) =&gt; {
 for (let i = 1; i &lt; arr.length; i++) {
 for (let j = i; j &amp;&amp; comparefn(arr[j-1], arr[j]) &gt; 0; j--) {
 [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
 }
 }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) =&gt; a - b);
console.log("" + array);

sort(array, (a, b) =&gt; b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) =&gt; a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));</code></pre>
</div>
</div>

Now the naive sort routine is generalized. You can see exactly when this callback is invoked, answering your first set of concerns:
<blockquote>
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
</blockquote>
Running the code below shows that, yes, the function is called many times and you can use <code>console.log</code> to see which numbers were passed in:
<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>const sort = (arr, comparefn) =&gt; {
 for (let i = 1; i &lt; arr.length; i++) {
 for (let j = i; j &amp;&amp; comparefn(arr[j-1], arr[j]) &gt; 0; j--) {
 [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
 }
 }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) =&gt; console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
 [3, 0, 4, 5].sort((a, b) =&gt; console.log(a, b) || (a - b))
);</code></pre>
</div>
</div>

You ask:
<blockquote>
How are the two sets of numbers then sorted in relation to one another?
</blockquote>
To be precise with terminology, <code>a</code> and <code>b</code> aren't sets of numbers--they're objects in the array (in your example, they're numbers).
The truth is, it doesn't matter how they're sorted because it's implementation-dependent. Had I used a different sort algorithm than insertion sort, the comparator would probably be invoked on different pairs of numbers, but at the end of the sort call, the invariant that matters to the JS programmer is that the result array is sorted according to the comparator, assuming the comparator returns values that adhere to the contract you stated (&lt; 0 when <code>a &lt; b</code>, 0 when <code>a === b</code> and &gt; 0 when <code>a &gt; b</code>).
In the same sense that I have the freedom to change my sort's implementation as long as I don't breach my specification, implementations of ECMAScript are free to choose the sort implementation within the confines of the <a href="https://tc39.es/ecma262/#sec-array.prototype.sort" rel="nofollow noreferrer">language specification</a>, so <code>Array#sort</code> will likely produce different comparator calls on different engines. One would not write code where the logic relies on some particular sequence of comparisons (nor should the comparator produce side effects in the first place).
For example, the V8 engine (at the time of writing) invokes <a href="https://github.com/v8/v8/blob/84cf890532510abda7ad4a8895fc8ad58799f1d1/third_party/v8/builtins/array-sort.tq#L5" rel="nofollow noreferrer">Timsort</a> when the array is larger than some precomputed number of elements and uses a <a href="https://github.com/v8/v8/blob/84cf890532510abda7ad4a8895fc8ad58799f1d1/third_party/v8/builtins/array-sort.tq#L490" rel="nofollow noreferrer">binary insertion sort</a> for small array chunks. However, it used to use <a href="https://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">quicksort</a> which is unstable and would likely give a different sequence of arguments and calls to the comparator.
Since different sort implementations use the return value of the comparator function differently, this can lead to surprising behavior when the comparator doesn't adhere to the contract. See <a href="https://stackoverflow.com/questions/52671125/why-does-sorting-a-js-array-of-numbers-with-work">this thread</a> for an example.

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

<pre><code>var array=[25, 8, 7, 41]

array.sort(function(a,b){
 return a - b
})
</code></pre>

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". 

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) = 17 (greater than zero, so sort "b" to be a lower index than "a"): 8, 25

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

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

Please help a struggling newbie!

How does Javascript's sort() work?

解释器

JSON

下面的代码如何按数字顺序对此数组进行排序？var array=[25, 8, 7, 41]array.sort(function(a,b){  return a - b})我知道如果计算的结果是...小于0："a“被排序为比"b”更低的索引。零： "a“和"b”被认为是相等的，不执行排序。大于0: "b“被排序为比"a...

问Javascript的sort()是如何工作的？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Javascript的sort()是如何工作的？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Javascript的sort()是如何工作的？
EN