Lianer

测试一下快速排序和冒泡排序的速度对比,快速排序法完胜冒泡排序法,但,原生sort函数秒杀了快速排序法。。。

// 快速排序法
function quickSort(arr, desc) {
    if(arr.length<2){
        return arr;
    }

    var base=arr[0], small=[], big=[];

    for (var i = 1, len=arr.length, n; i<len; i++) {
        count.quick++;
        n=arr[i];
        if(n<base){
            small.push(n);
        }
        else{
            big.push(n);
        }
    };

    if(desc){
        return quickSort(big, true).concat(base).concat(quickSort(small, true));
    }
    else{
        return quickSort(small).concat(base).concat(quickSort(big));
    }
}
// 冒泡排序法
function bubbleSort(arr, desc) {
    for (var i = 0, len = arr.length, temp; i < len; i++) {
        for (var j = i + 1; j < len; j++) {
            count.bubble++;
            if (desc) {
                if (arr[j] > arr[i]) {
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            } else {
                if (arr[j] < arr[i]) {
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        };
    };
    return arr;
}

对20,000个数据进行测试,其中快速排序法一共走了330,574次循环(71ms),而冒泡排序约2亿次循环(980ms)。数据长度越大,快速排序的优势约明显。

但又测试了一下js原生的sort函数,发现只走了32,174次循环(22ms),不知道用的是什么算法?