JavaScript Array#sort()
函数使用哪种算法?我知道它可以采用各种方式的参数和函数来执行不同类型的排序,我只是对普通排序使用哪种算法感兴趣。
最佳答案
我刚刚浏览了 WebKit(Chrome、Safari ...)source 。根据数组的类型,使用不同的排序方法:
Numeric arrays (或基本类型的数组)使用 C++ 标准库函数 std::qsort
进行排序它实现了快速排序的一些变体(通常 introsort )。
Contiguous arrays of non-numeric type如果可用的话,使用归并排序(以获得稳定的排序)进行字符串化和排序,如果没有可用的归并排序,则使用 qsort
进行排序。
对于其他类型(非连续数组和可能的关联数组),WebKit 使用 selection sort (他们称之为 “min” sort ),或者在某些情况下,它通过 AVL 树排序。不幸的是,这里的文档相当模糊,因此您必须跟踪代码路径才能实际查看哪些类型使用了哪种排序方法。
还有像 this comment 这样的 gem :
// 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).
– 我们只希望真正“修复”这个问题的人比此评论的作者对渐近运行时有更好的理解,并意识到 radix sort has a slightly more complex runtime description而不是简单的 O(N)。
(感谢 phsource 指出原答案中的错误。)
关于Javascript Array.sort 实现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40338857/