ChromeV8的sort排序简单实现

2017-10-29

V8 sort实现

原理：V8的sort是在数组顺序小于10的时候调用的是插入排序，大于10的时候调用的快速排序

function quickSort(arr, fn) {
    var left = [];
    var right = [];
    if (arr.length <= 1) return arr;
    var ele = arr.splice(Math.floor(arr.length / 2), 1)[0]
    for (var i = 0; i < arr.length; i++) {
        if (fn(arr[i], ele)) {
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    return quickSort(left, fn).concat([ele], quickSort(right, fn))
}
function insertSort(arr, fn) {
    for(var i = 1; i < arr.length ; i++) {
        var insertEl = arr[i];
        for(var j = i - 1; j >= 0; j--) {
            if (fn(arr[j], insertEl)) {
                arr[j + 1] = arr[j]
            } else {
                break;
            }
        }
        arr[j + 1] = insertEl;
    }
}
//传入fn,通过对fn的定制可以针对性的对数组中元素的排序，比如倒序、对象的排序
function v8Sort(arr, fn) {
    if (!fn) {
        fn = function (a, b) {return a - b >= 0;}
    }
    if (arr.length <= 10) {
        insertSort(arr, fn)
    } else {
        var arr = quickSort(arr, fn)
    }
    return arr;
}