到底问题出在哪里，第二次的时间要么是0，要么是1，函数执行位置更换之后还是一样

Question

只有数组长度大于1000的时候，插入排序的优势才会出来，而在1000以下，先执行插入后执行排序，排序所用的时间要么是0毫秒，要么事1毫秒，而当把插入和排序函数执行的顺序换一下【数组长度还是在1000以内】插入的执行时间就变成要么是0毫秒，要么是1毫秒了。

总结了说就是在数组很短的时候，谁先执行，谁的耗时就长，而当数组足够大的时候，不管谁先执行，插入的执行时间总是比排序短。

var arr = [];
var arr2 = [];
function generateRandomArray(n,l,r) {
    arr = new Array(n);
    for(let i = 0; i<n;i++){
        arr[i] = Math.floor(Math.random()*(r-l))+l;
    }
    return arr;
}
function fntime(fn) {
    let start = new Date().getTime(); // 开始时间
    fn()
    let end = new Date().getTime(); // 结束时间
    console.log(end - start+"毫秒！");
}
function copyArray(arr) {
    for(let i = 0; i<arr.length;i++){
        arr2.push(arr[i]);
    }
}
function main() {
    arr = generateRandomArray(100,0,100000);
    copyArray(arr)
    fntime(insertSort)
    console.log("----------------------------------------------------------------------")
    fntime(selectionSort)
}
//var arr = ["f","u","c","K","o","x"];
function insertSort() {
    for(let i = 1; i < arr.length; i++){
        let e =arr[i];
        let j = 0;
        for(j = i; j > 0; j--){
            if(arr[j-1] > e){
                arr[j] = arr[j-1];
            }else {
                break
            }
        }
        arr[j] = e;
    }
    console.log("我是插入排序"+arr)
}
function selectionSort() {
    for(let i = 0; i < arr2.length; i++){
        let minIndex = i;
        for(let j = i+1; j < arr2.length; j++){
            if(arr2[j] < arr2[minIndex]){
                [arr2[j],arr2[minIndex]] = [arr2[minIndex],arr2[j]];
            }
        }
    }
    console.log("我是选择排序"+arr2)
}
main()

Answer 1

liuyubobobo 2017-02-17 21:41:39

算法性能测试，在数据量比较小的情况下，意义不大。由于对于脚本语言，执行器是直接运行的，所以第一次执行的时候很多时间是和机器当时的状态相关的，而不完全是算法相关的。0毫秒还是1毫秒，都是Data函数能测试的时间的最小单位，这两个数字近乎就是一样的。所以测试算法的性能，还是需要大样本才能测出来。

• 提问者 拖车板牙爵士 #1

  为什么老师用c语言优化插入排序的时候，100的数组比较插入跟排序，而插入也能表现出明显的优势，是否是语言本身的问题？

• liuyubobobo 回复 提问者 拖车板牙爵士 #2

  课程中是对n=10000的情况进行的测试哦：）

• 提问者 拖车板牙爵士 #3

  非常感谢！