javascript 算法整理

摘要：快速排序快速排序原始数组二分查找冒泡排序冒泡排序耗时冒泡排序耗时改进后的冒泡排序耗时改进后的冒泡排序耗时排序前冒泡排序后改进的冒泡排序后选择排序选择排序耗时选择排序耗时排序前排序后插入排序插入排序耗时插入排序耗时排序前排序后

function quickSort(ary, isDesc) {
    var len = ary.length;
    if (len < 3) {
        return ary;
    }
    var baseIndex = Math.floor(len / 2),
        base = ary[baseIndex];
    var smallAry = [],
        largeAry = [];
    for (var i = len - 1, cur; i > -1; i--) {
        cur = ary[i];
        if (i == baseIndex) {
            continue;
        }
        if (isDesc) {
            cur < base ? (largeAry[largeAry.length] = cur) : (smallAry[smallAry.length] = cur);
        } else {
            cur >= base ? (largeAry[largeAry.length] = cur) : (smallAry[smallAry.length] = cur);
        }
    }
    smallAry[smallAry.length] = base;
    return quickSort(smallAry, isDesc).concat(quickSort(largeAry, isDesc));
}

function halfSearch(ary, num) {
    var len = ary.length,
        middle = Math.floor(len / 2),
        midNum = ary[middle];
    if (len == 0) {
        return null;
    } else if (num === midNum) {
        return midNum;
    } else if (midNum > num ) {
        return halfSearch(ary.slice(0, middle), num);
    } else {
        return halfSearch(ary.slice(middle + 1), num);
    }
}

var testAry = [9, 2, 3, 4, 1, 0, 8, 4, 2];
var sortedAry = quickSort(testAry);
console.log(sortedAry, "快速排序");
console.log(testAry, "原始数组");
console.log(halfSearch(sortedAry, 3), "二分查找");

var common = require("./common");

function bubbleSort(ary){
    console.time("冒泡排序耗时");
    var len = ary.length;
    for(var i = 0; i < len; i++){
        for(var j = 0; j < len-1-i; j++){
            if(ary[j] > ary[j+1]){
                var tmp = ary[j];
                ary[j] = ary[j+1];
                ary[j+1] = tmp;
            }
        }
    }
    console.timeEnd("冒泡排序耗时");
    return ary;
}

function bubbleSort2(ary){
    console.time("改进后的冒泡排序耗时");
    var i = ary.length -1;
    while(i > 0){
        var pos;
        for(var j = 0; j < i; j++){
            if(ary[j] > ary[j+1]){
                pos = j;
                var tmp = ary[j];
                ary[j] = ary[j+1];
                ary[j+1] = tmp;
            }
            i = pos;
        }
    }
    console.timeEnd("改进后的冒泡排序耗时");
    return ary;
}

var ary = common.createAry(200);
console.log("排序前", ary.toString());
var result = bubbleSort(ary);
console.log(result.toString(), "冒泡排序后");
console.log(tmp.toString());
result = bubbleSort2(tmp);
console.log(result.toString(), "改进的冒泡排序后");

var common = require("./common");
function chooseSort(ary){
    console.time("选择排序耗时");
    var len = ary.length,
        tmp, minIndex;
    for(var i = 0; i < len; i++){
        minIndex = i;
        for(j = i+1; j < len - i; j++){
            if(ary[j] < ary[minIndex]){
                minIndex = j;
            }
        }
        tmp = ary[i];
        ary[i] = ary[minIndex];
        ary[minIndex] = tmp;
    }
    console.timeEnd("选择排序耗时");
    return ary;
}

var ary = common.createAry(20);
console.log("排序前", ary);
var sortedAry = chooseSort(ary);
console.log("排序后", sortedAry);

var common = require("./common");
function insertSort(ary) {
    console.time("插入排序耗时");
    var len = ary.length;
    for (var i = 1; i < len; i++) {
        var key = ary[i],
            j = i - 1;
        while (j >= 0 && key < ary[j]) {
            ary[j + 1] = ary[j];
            j--;
        }
        ary[j + 1] = key;
    }
    console.timeEnd("插入排序耗时");
    return ary;
}

var ary = common.createAry(20);
console.log("排序前", ary);
var sortedAry = insertSort(ary);
console.log("排序后", sortedAry);

exports.createAry =  function(number){
    var ary = [];
    for(let i = 0; i < number; i++){
        ary.push(Math.floor(Math.random()*100));
    }
    return ary;
}