javascript中sort()和indexOf()内部使用了什么算法 时间复杂度是多少

Question

这是一道字节跳动的面试题
sort()是内部使用了什么算法 时间复杂度是多少 indexOf()的时间复杂度是多少
知道一个就请回答一下
有人知道怎么去知道这内部到底用了什么吗，也就是sort和indexOf的源码在哪里

Answer 1

ES 规范并没有指定具体的算法，我对 V8/Chrome/Node 比较熟悉，说说 V8 的 sort 算法吧。

在 Chrome 70 以前，sort 的算法比较特殊：

• 当元素个数小于 10 个的时候，使用插入排序；
• 当元素个数大于 10 个的时候，使用快速排序。

众所周知：插入排序是稳定的，快速排序是并不稳定的。

从 Chrome 70 开始，V8 团队更新了排序算法，使用了 Timsort 算法。

Answer 2

例如sort 。ECMAScript没有定义使用哪种排序算法，各个浏览器的实现方式会有不同（归并或者快排或者其他？）。具体的复杂度也难说，基本是nlogn或者以下?

Answer 3

sort的话，其实不同浏览器不同，并且同一个浏览器也会根据不同条件用不同算法。
之前看到过chrome的，不过记不太清楚了，元素很少的时候可能就是插入排序，多了以后可能就是快排之类的，复杂度是O(nlogn)。
至于indexOf复杂度摊销应该是O(n)

Answer 4

ECMAScript 没定义具体算法，

所以这里基本问的都是v8的实现；
sort 使用了timsort ，查看源码，详细解释可以网上搜索一下

indexOf, 我猜是遍历数组