chrome浏览器中,javascript数组sort函数采用的什么排序算法?

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;
});

输出的结果为:
v2-6f300f41dbdcd6541b02e243c3957de6_b.png
看着输出结果,愣是没有推理出sort的排序算法,心塞呀。js大神帮我看看哈。

阅读 8.3k
5 个回答

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 源码

这个是插入排序

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) 的返回值来排序的。

推荐问题
宣传栏