blocks|key|1707742|text|我刚刚看了一下WebKit+(Chrome，Safari…)source。根据数组的类型，使用不同的排序方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1707743|使用C%2B%2B标准库函数std::qsort对快速排序(或原始类型数组)进行排序，该函数实现了快速排序的一些变体(通常是introsort)。|style|CODE|1707744|如果Contiguous+arrays+of+non-numeric+type可用(以获得稳定的排序)，则使用mergesort进行字符串标识和排序；如果没有merge+sort可用，则使用qsort进行排序。|1707745|对于其他类型(非连续数组和关联数组)，WebKit使用selection+sort+(他们称之为“min”+sort)，或者在某些情况下，它通过AVL树进行排序。不幸的是，这里的文档相当模糊，所以您必须跟踪代码路径才能真正了解使用了哪种类型和排序方法。|1707746|然后是像this+comment这样的宝石|1707747|//+FIXME:+Since+we+sort+by+string+value,+a+fast+algorithm+might+be+to+use+a
//+radix+sort.+That+would+be+O(N)+rather+than+O(N+log+N).|code-block|syntax|javascript|1707748|-让我们只希望实际“修复”它的人比这篇评论的作者更好地理解渐近运行时，并意识到radix+sort+has+a+slightly+more+complex+runtime+description而不是简单的O(N)。|1707749|(感谢phsource指出了原始答案中的错误。)|1707750|entityMap|0|LINK|mutability|MUTABLE|url|http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp?rev=138530#L647|1|http://en.cppreference.com/w/cpp/algorithm/qsort|2|https://en.wikipedia.org/wiki/Introsort|3|http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L1065|4|http://en.wikipedia.org/wiki/Selection_Sort|5|http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp?rev=138530#L668|6|http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L1124|7|https://stackoverflow.com/a/474040/1968^0|U|6|0|0|A|A|A|A|1|1M|9|2|0|2N|5|2|11|3|0|R|E|4|1C|A|5|0|4|C|6|0|0|13|1M|7|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@]|9|@$A|1J|B|1K|1|1L]]|C|$]]|$1|D|3|E|5|6|7|1M|8|@$A|1N|B|1O|F|G]]|9|@$A|1P|B|1Q|1|1R]|$A|1S|B|1T|1|1U]]|C|$]]|$1|H|3|I|5|6|7|1V|8|@$A|1W|B|1X|F|G]]|9|@$A|1Y|B|1Z|1|20]]|C|$]]|$1|J|3|K|5|6|7|21|8|@]|9|@$A|22|B|23|1|24]|$A|25|B|26|1|27]]|C|$]]|$1|L|3|M|5|6|7|28|8|@]|9|@$A|29|B|2A|1|2B]]|C|$]]|$1|N|3|O|5|P|7|2C|8|@]|9|@]|C|$Q|R]]|$1|S|3|T|5|6|7|2D|8|@]|9|@$A|2E|B|2F|1|2G]]|C|$]]|$1|U|3|V|5|6|7|2H|8|@]|9|@]|C|$]]|$1|W|3|-4|5|6|7|2I|8|@]|9|@]|C|$]]]|X|$Y|$5|Z|10|11|C|$12|13]]|14|$5|Z|10|11|C|$12|15]]|16|$5|Z|10|11|C|$12|17]]|18|$5|Z|10|11|C|$12|19]]|1A|$5|Z|10|11|C|$12|1B]]|1C|$5|Z|10|11|C|$12|1D]]|1E|$5|Z|10|11|C|$12|1F]]|1G|$5|Z|10|11|C|$12|1H]]]]

I've just had a look at the WebKit (Chrome, Safari …) <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp?rev=138530#L647" rel="noreferrer">source</a>. Depending on the type of array, different sort methods are used:

<a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L972" rel="noreferrer">Numeric arrays</a> (or arrays of primitive type) are sorted using the C++ standard library function <a href="http://en.cppreference.com/w/cpp/algorithm/qsort" rel="noreferrer"><code>std::qsort</code></a> which implements some variation of quicksort (usually <a href="https://en.wikipedia.org/wiki/Introsort" rel="noreferrer">introsort</a>).

<a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L1065" rel="noreferrer">Contiguous arrays of non-numeric type</a> are stringified and sorted using mergesort, if available (to obtain a stable sorting) or <code>qsort</code> if no merge sort is available.

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either <a href="http://en.wikipedia.org/wiki/Selection_Sort" rel="noreferrer">selection sort</a> (which they call <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp?rev=138530#L668" rel="noreferrer">“min” sort</a>) or, in some cases, it sorts via an AVL tree. Unfortunately, the documentation here is rather vague so you’d have to trace the code paths to actually see for which types which sort method is used.

And then there are gems like <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L1124" rel="noreferrer">this comment</a>:

<pre><code>// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).
</code></pre>

– Let’s just hope that whoever actually “fixes” this has a better understanding of asymptotic runtime than the writer of this comment, and realises that <a href="https://stackoverflow.com/a/474040/1968">radix sort has a slightly more complex runtime description</a> than simply O(N).

(Thanks to phsource for pointing out the error in the original answer.)

blocks|key|1492664|text|如果你看一下这个bug+224128，就会发现Mozilla正在使用MergeSort。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1492665|entityMap|0|LINK|mutability|MUTABLE|url|https://bugzilla.mozilla.org/show_bug.cgi?id=224128^0|C|6|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

If you look at this bug <a href="https://bugzilla.mozilla.org/show_bug.cgi?id=224128" rel="noreferrer">224128</a>, it appears that MergeSort is being used by Mozilla.

blocks|key|1492610|text|ECMAscript标准没有指定要使用哪种排序算法。实际上，不同的浏览器具有不同的排序算法。例如，在对地图进行排序时，Mozilla/Firefox的stable+()不是排序(从单词的排序意义上讲)。IE的sort()是稳定的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1492611|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Sorting_algorithm#Stability^0|23|6|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

The ECMAscript standard does not specify which sort algorithm is to be used. Indeed, different browsers feature different sort algorithms. For example, Mozilla/Firefox's sort() is not <a href="http://en.wikipedia.org/wiki/Sorting_algorithm#Stability" rel="noreferrer">stable</a> (in the sorting sense of the word) when sorting a map. IE's sort() is stable.

blocks|key|1707547|text|我认为这将取决于您所指的浏览器实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1707548|每种浏览器类型都有自己的javascript引擎实现，所以要视情况而定。您可以查看Mozilla和Webkit/Khtml的源码代码库以了解不同的实现。|1707549|IE是封闭源码的，所以你可能需要去问微软的人。|1707550|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

I think that would depend on what browser implementation you are refering to.

Every browser type has it's own javascript engine implementation, so it depends.
You could check the sourcecode repos for Mozilla and Webkit/Khtml for different implementations.

IE is closed source however, so you may have to ask somebody at microsoft.

blocks|key|1707650|text|经过进一步的研究，似乎对于Mozilla/Firefox，Array.sort()使用了合并排序。请参阅代码here。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1707651|entityMap|0|LINK|mutability|MUTABLE|url|https://dxr.mozilla.org/seamonkey/source/js/src/jsarray.c^0|1I|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code <a href="https://dxr.mozilla.org/seamonkey/source/js/src/jsarray.c" rel="noreferrer">here</a>.

blocks|key|1707798|text|从PythonV7.0/Chrome70开始，V8使用V8的排序算法TimSort。Chrome+70于2018年9月13日发布。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1707799|有关此更改的详细信息，请参阅the+post+on+the+V8+dev+blog。您还可以读取source+code或patch+1186801。|1707800|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Timsort|1|https://v8.dev/blog/array-sort|2|https://chromium.googlesource.com/v8/v8.git/%2B/master/third_party/v8/builtins/array-sort.tq|3|https://chromium-review.googlesource.com/c/v8/v8/%2B/1186801^0|Y|7|0|0|E|R|1|1C|B|2|1O|D|3|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@$A|Y|B|Z|1|10]|$A|11|B|12|1|13]|$A|14|B|15|1|16]]|C|$]]|$1|F|3|-4|5|6|7|17|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]|P|$5|I|J|K|C|$L|Q]]|R|$5|I|J|K|C|$L|S]]]]

As of V8 v7.0 / Chrome 70, V8 uses <a href="https://en.wikipedia.org/wiki/Timsort" rel="nofollow noreferrer">TimSort</a>, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.
See the <a href="https://v8.dev/blog/array-sort" rel="nofollow noreferrer">the post on the V8 dev blog</a> for details about this change. You can also read the <a href="https://chromium.googlesource.com/v8/v8.git/+/master/third_party/v8/builtins/array-sort.tq" rel="nofollow noreferrer">source code</a> or <a href="https://chromium-review.googlesource.com/c/v8/v8/+/1186801" rel="nofollow noreferrer">patch 1186801</a>.

blocks|key|1492866|text|尝试使用快速排序：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1492867|function+sort(arr,+compareFn+=+(a,+b)+=>+a+<=+b)+{

++++if+(!arr+instanceof+Array+%7C%7C+arr.length+===+0)+{
++++++++return+arr;
++++}

++++if+(typeof+compareFn+!==+'function')+{
++++++++throw+new+Error('compareFn+is+not+a+function!');
++++}

++++const+partition+=+(arr,+low,+high)+=>+{
++++++++const+pivot+=+arr[low];
++++++++while+(low+<+high)+{
++++++++++++while+(low+<+high+&&+compareFn(pivot,+arr[high]))+{
++++++++++++++++--high;
++++++++++++}
++++++++++++arr[low]+=+arr[high];
++++++++++++while+(low+<+high+&&+compareFn(arr[low],+pivot))+{
++++++++++++++++%2B%2Blow;
++++++++++++}
++++++++++++arr[high]+=+arr[low];
++++++++}
++++++++arr[low]+=+pivot;
++++++++return+low;
++++};

++++const+quickSort+=+(arr,+low,+high)+=>+{
++++++++if+(low+<+high)+{
++++++++++++let+pivot+=+partition(arr,+low,+high);
++++++++++++quickSort(arr,+low,+pivot+-+1);
++++++++++++quickSort(arr,+pivot+%2B+1,+high);
++++++++}
++++++++return+arr;
++++};

++++return+quickSort(arr,+0,+arr.length+-+1);
}|code-block|syntax|javascript|1492868|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|$]]

try this with quick sort:

<pre><code>function sort(arr, compareFn = (a, b) =&gt; a &lt;= b) {

 if (!arr instanceof Array || arr.length === 0) {
 return arr;
 }

 if (typeof compareFn !== 'function') {
 throw new Error('compareFn is not a function!');
 }

 const partition = (arr, low, high) =&gt; {
 const pivot = arr[low];
 while (low &lt; high) {
 while (low &lt; high &amp;&amp; compareFn(pivot, arr[high])) {
 --high;
 }
 arr[low] = arr[high];
 while (low &lt; high &amp;&amp; compareFn(arr[low], pivot)) {
 ++low;
 }
 arr[high] = arr[low];
 }
 arr[low] = pivot;
 return low;
 };

 const quickSort = (arr, low, high) =&gt; {
 if (low &lt; high) {
 let pivot = partition(arr, low, high);
 quickSort(arr, low, pivot - 1);
 quickSort(arr, pivot + 1, high);
 }
 return arr;
 };

 return quickSort(arr, 0, arr.length - 1);
}
</code></pre>

blocks|key|1707888|text|JavaScript的Array.sort()函数具有根据数组元素的数据类型选择最佳排序算法(+QuickSort、MergeSort等)的内部机制。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1707889|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

JavaScript's Array.sort() function has internal mechanisms to selects the best sorting algorithm ( QuickSort, MergeSort, etc) on the basis of the datatype of array elements.

Which algorithm does the JavaScript <code>Array#sort()</code> function use? I understand that it can take all manner of arguments and functions to perform different kinds of sorts, I'm simply interested in which algorithm the vanilla sort uses.

Javascript Array.sort implementation?

JavaScript Array#sort()函数使用哪种算法？我知道它可能需要各种各样的参数和函数来执行不同种类的排序，我只是对vanilla排序使用哪种算法感兴趣。

问Javascript Array.sort实现？
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Javascript Array.sort实现？EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Javascript Array.sort实现？
EN