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

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

阅读 10.2k
4 个回答

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

在 Chrome 70 以前,sort 的算法比较特殊:

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

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

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

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

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

ECMAScript 没定义具体算法,

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

indexOf, 我猜是遍历数组

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
宣传栏