冒泡排序

/*
冒泡排序
*/
let arr = [1,5,2,9,8,7,3,4,6];

function sortArray(arr){
    let temp;
    for(let i=0; i<arr.length - 1; i++){
        for(let j=0; j<arr.length -1; j++){
            if(arr[j]>arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            }
        }
    }
}
console.log("原始方法 ========================");
printTime(sortArray, 100000);


//改进1：设置标志位pos，每一层排完序之后，就记录排到最大的哪一位在什么位置，因为每一层最大的数就是它所在数组的倒数的位数,下一次就没必要再循环一遍

function sortArray1(arr){
    let i = arr.length -1;
    while(i>0){
        let pos = 0;
        for(let j=0; j<i; j++){
            if(arr[j]>arr[j+1]){
                pos = j;
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        i = pos;
    }
}

console.log("改进方法1 ========================");
printTime(sortArray1, 100000);


//改进2：每趟排序从正反向冒泡一次得到两个最终值(最大和最小值)，排序次数几乎减少一半
function sortArray2(arr){
    let low = 0;
    let high = arr.length -1;
    while(low < high){
        for(let i = low; i < high; i++){
            if(arr[i]>arr[i+1]){
                let temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        --high;
        for(let j = high; j> low; j--){
            if(arr[j]<arr[j-1]){
                let temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        ++low;
    }
}

console.log("改进方法2 ========================");
printTime(sortArray2, 100000);

/* 三种方法在数据量为 10000和1000000时的差距如下：
原始方法 ========================
VM1255 algorithm:84 方法耗时： 309
VM1255 algorithm:43 改进方法1 ========================
VM1255 algorithm:84 方法耗时： 183
VM1255 algorithm:75 改进方法2 ========================
VM1255 algorithm:84 方法耗时： 175
VM1255 algorithm:1 undefined
algorithm:21 原始方法 ========================
algorithm:84 方法耗时： 34057
algorithm:43 改进方法1 ========================
algorithm:84 方法耗时： 22726
algorithm:75 改进方法2 ========================
algorithm:84 方法耗时： 16544

*/




//时间工具
function printTime(func, scope){
    let preTime = new Date().getTime();
    func(getIntArr(scope));
    let curTime = new Date().getTime();
    console.log("方法耗时：", curTime-preTime);
}

//获取一个整型数组
function getIntArr(scope){
    let arr = [];
    for(let i = 0; i<scope; i++){
        let temp = parseInt(Math.random()*i);
        arr.push(temp);
    }
    return arr;
}