我刚刚看过WebKit(Chrome、Safari…)source.根据数组的类型,使用不同的排序方法:
使用C++标准库函数std::qsort
对Numeric arrays(或基元类型数组)进行排序,该C++标准库函数std::qsort
实现快速排序的一些变体(通常是introsort).
如果可用(以获得稳定的排序),则使用mergesort对Contiguous arrays of non-numeric type进行字符串化和排序;如果没有可用的合并排序,则使用qsort
进行字符串化和排序.
对于其他类型(非连续数组和可能用于关联数组),WebKit使用selection sort(他们称之为“min” sort),或者在某些情况下,它通过AVL树进行排序.不幸的是,这里的文档相当模糊,所以您必须跟踪代码路径才能真正了解哪些类型使用了哪种排序方法.
还有像this comment这样的Ruby :
// 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指出原始答案中的错误.)