Javascript Array.sort 实现? [英] Javascript Array.sort implementation?

问题描述

JavaScript Array#sort() 函数使用哪种算法?我知道它可以使用各种参数和函数来执行不同种类的排序，我只是对普通排序使用的算法感兴趣.

Which algorithm does the JavaScript Array#sort() 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.

推荐答案

我刚刚看了看 WebKit(Chrome、Safari ...)源.根据数组的类型，使用不同的排序方法:

I've just had a look at the WebKit (Chrome, Safari …) source. Depending on the type of array, different sort methods are used:

数字数组(或原始类型的数组)使用 C++ 标准库函数进行排序 std::qsort 实现了快速排序的一些变体(通常是introsort).

Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function std::qsort which implements some variation of quicksort (usually introsort).

非数字的连续数组类型 使用归并排序进行字符串化和排序，如果可用(以获得稳定排序)或 qsort 如果没有归并排序可用.

Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or qsort if no merge sort is available.

对于其他类型(非连续数组和关联数组)，WebKit 使用 选择排序 (他们称之为 min" sort) 或者，在某些情况下，它通过 AVL 树进行排序.不幸的是，这里的文档相当模糊，因此您必须跟踪代码路径才能实际查看使用哪种排序方法的类型.

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call "min" sort) 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.

然后还有像 这条评论:

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

——我们只希望真正修复"这个问题的人比这篇评论的作者对渐近运行时有更好的理解，并意识到 基数排序的运行时描述比简单的 O(N) 稍微复杂一些.

– 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 radix sort has a slightly more complex runtime description than simply O(N).

(感谢 phsource 指出原始答案中的错误.)

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

这篇关于Javascript Array.sort 实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！