chrome浏览器下,javascript的sort函数用的什么排序算法?
let arr=[1,99,4,20,8,13,5,67,32,50];
arr.sort((a,b)=>{
console.log(a, b);
return a-b;
});
输出的结果为:
看着输出结果,愣是没有推理出sort的排序算法,心塞呀。js大神帮我看看哈。
chrome浏览器下,javascript的sort函数用的什么排序算法?
let arr=[1,99,4,20,8,13,5,67,32,50];
arr.sort((a,b)=>{
console.log(a, b);
return a-b;
});
输出的结果为:
看着输出结果,愣是没有推理出sort的排序算法,心塞呀。js大神帮我看看哈。
这个是插入排序
function insertSort(arr) {
var res = [arr[0]];
for (let i = 1, len = arr.length; i < len; i++) {
let temp = arr[i];
for (let j = i - 1; j >= 0; j--) {
console.log(res[j], arr[i]);
if (res[j] > temp) {
res[j + 1] = res[j];
res[j] = temp;
} else {
res[j + 1] = temp;
break;
}
}
}
return res;
}
可以参考zollero的解释
大神的解释
可以理解为使用冒泡排序的原理。
示例简化如下:
var array = [10,5,40,25,1000,1];
array.sort(compareFunction);
function compareFunction(a, b) {
return a - b;
}
console.log(array);
参数a和b,就是依次从array数组中取连续的两个元素,如从示例中先选择前两个元素:10, 5。
所以,在匿名函数内 a - b 的结果是 5。
再看下,匿名函数的结果跟排序的关系:
如果 compareFunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前;
如果 compareFunction(a, b) 等于 0 , a 和 b 的相对位置不变。备注:ECMAScript 标准并不保证这一行为,而且也不是所有浏览器都会遵守(例如 Mozilla 在 2003 年之前的版本);
如果 compareFunction(a, b) 大于 0 , b 会被排列到 a 之前。
compareFunction(a, b) 必须总是对相同的输入返回相同的比较结果,否则排序的结果将是不确定的。
所以,示例是按照 compareFunction(a, b) 的返回值来排序的。
8 回答3.8k 阅读✓ 已解决
6 回答1.7k 阅读✓ 已解决
5 回答5.5k 阅读✓ 已解决
4 回答1.8k 阅读✓ 已解决
3 回答1.9k 阅读
4 回答2.4k 阅读✓ 已解决
3 回答2.1k 阅读✓ 已解决
Mozilla/Firefox : 归并排序(jsarray.c 源码)
V8 :数组长度小于等于 22 的用插入排序,其它的用快速排序(array.js 源码)见下面注释
// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.
Webkit :底层实现用了 C++ 库中的 qsort() 方法(JSArray.cpp 源码)