用console.time(字符串)和console.timeEnd(字符串)组合可以判断时间
先看下, 冒泡, 快排, 系统冒泡, 三种排序结果时间比较

可以看到, 一般情况下快排最快, 修改后的冒泡比系统自带冒泡快些(因为有排序后就停止了, 系统的一定要全扫描就算已经排序好了)

快排

想想一拳超人的根据中心快速左右移动, 就是取一个数作为基准, 大于它的放在右边, 小于放左边

function quickSort(arr) {
    // 递归出口, 长度小于等于0 的时候就要退出了
    if (arr.length <= 0 ) return arr;

    var base = arr[0];
    var left = [];
    var right = [];

    for (var i = 1; i< arr.length; i++) {
        if (arr[i] < base) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([base], quickSort(right));
}

测试用例

// -------------------- 测试用例 --------------------------
var arr = [89,56,89,54,21,4657,4,3,8,6,7,9,45,26,56]; // 输入15个元素
console.log("排序初始数组: "+arr);
console.time("quickSort");
// [3, 4, 6, 7, 8, 9, 21, 26, 45, 54, 56, 56, 89, 89, 4657]
console.log("快排结果: "+quickSort(arr));
console.timeEnd("quickSort"); // quickSort: 3770.940185546875ms

冒泡排序

用交换的方式, 每次把最值找出来排序

在数组数量小的时候冒泡还是比较快的

两层循环一次次把最大值或最小值排序到相应位置, 要从大到小或从小到大更改下比较就好了

通过我的调查我发现, 对于算法不了解的人最一开始想到的是:

1. 简单选择排序 通过选择找最值

2. 冒泡排序 通过交换找最值

// -------------------- 冒泡排序 ----------------------------
function bubbleSort(arr) {
    var change = true;
    // 外层循环
    for (var i = 0;i < arr.length; i++) {
        // 需要定义一个flag 用于判断该次已经排序完毕了, 不然会有冗余扫描
        change = true;
        // 内层循环
        for (var j = i; j < arr.length; j++) {
            if (arr[i] >= arr[j]) {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                // 说明改变过了
                change = false;
            }
        }

        if (change === true) break;
    }
    return arr;
}

测试用例

// -------------------- 测试用例 --------------------------
var arr = [89,56,89,54,21,4657,4,3,8,6,7,9,45,26,56]; // 输入15个元素
console.log("排序初始数组: "+arr);
console.time("bubbleSort");
// 叠加时间判断速度
for(var i = 0; i<1000000; i++) {
    bubbleSort(arr);
}
// [3, 4, 6, 7, 8, 9, 21, 26, 45, 54, 56, 56, 89, 89, 4657]
console.log("冒泡排序结果: "+ bubbleSort(arr));
console.timeEnd("bubbleSort"); //bubbleSort: 167.6572265625ms

系统默认sort排序

也是冒泡方式的一种, 区别是没有设置flag意思是一定是O(n^2)一定要循环到n^2

// -------------- 系统默认排序 --------------------
console.time("defaultSort");
for(var i = 0; i<1000000; i++) {
    arr.sort(function (a, b) {
        return a-b;
    });// 系统的默认排序方法
}

测试用例

// -------------------- 测试用例 --------------------------
var arr = [89,56,89,54,21,4657,4,3,8,6,7,9,45,26,56]; // 输入15个元素
console.log("排序初始数组: "+arr);
// [3, 4, 6, 7, 8, 9, 21, 26, 45, 54, 56, 56, 89, 89, 4657]
console.log("系统默认sort排序: "+arr.sort(function (a, b) {
    return a-b;
}));
console.timeEnd("defaultSort"); // defaultSort: 452.140869140625ms