用
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
冒泡排序
用交换的方式, 每次把最值找出来排序
在数组数量小的时候冒泡还是比较快的
两层循环一次次把最大值或最小值排序到相应位置, 要从大到小或从小到大更改下比较就好了
通过我的调查我发现, 对于算法不了解的人最一开始想到的是:
简单选择排序
通过选择找最值
冒泡排序
通过交换找最值
// -------------------- 冒泡排序 ----------------------------
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
网友评论