这是一道字节跳动的面试题
sort()是内部使用了什么算法 时间复杂度是多少 indexOf()的时间复杂度是多少
知道一个就请回答一下
有人知道怎么去知道这内部到底用了什么吗,也就是sort和indexOf的源码在哪里
这是一道字节跳动的面试题
sort()是内部使用了什么算法 时间复杂度是多少 indexOf()的时间复杂度是多少
知道一个就请回答一下
有人知道怎么去知道这内部到底用了什么吗,也就是sort和indexOf的源码在哪里
sort的话,其实不同浏览器不同,并且同一个浏览器也会根据不同条件用不同算法。
之前看到过chrome的,不过记不太清楚了,元素很少的时候可能就是插入排序,多了以后可能就是快排之类的,复杂度是O(nlogn)。
至于indexOf复杂度摊销应该是O(n)
ECMAScript 没定义具体算法,
所以这里基本问的都是v8的实现;sort
使用了timsort ,查看源码,详细解释可以网上搜索一下
indexOf
, 我猜是遍历数组
8 回答4.1k 阅读✓ 已解决
6 回答2.5k 阅读✓ 已解决
5 回答2.3k 阅读✓ 已解决
5 回答5.8k 阅读✓ 已解决
4 回答2k 阅读✓ 已解决
3 回答2.1k 阅读
4 回答2.6k 阅读✓ 已解决
ES 规范并没有指定具体的算法,我对 V8/Chrome/Node 比较熟悉,说说 V8 的
sort
算法吧。在 Chrome 70 以前,
sort
的算法比较特殊:10
个的时候,使用插入排序;10
个的时候,使用快速排序。众所周知:插入排序是稳定的,快速排序是并不稳定的。
从 Chrome 70 开始,V8 团队更新了排序算法,使用了 Timsort 算法。