记一次冒泡、插入、归并排序的时间比较

正文

直入正题

两个关键变量

size:产生的随机数组的长度,随机数组中的每一项为 Math.round(1000 * Math.random())

n:实验的次数

结论:

  • 冒泡排序:弟中弟
  • 插入排序:相对弟弟
  • 归并排序:你们都是弟弟

n = 50000 size = 100的情况下

n(次数) size(随机数组的长度) 冒泡排序(s) 插入排序(s) 归并排序(s)
10 5000 0.568 0.272 0.019
10 10000 2.531 1.347 0.029
10 50000 77.843 32.226 0.168
10000 50 1.975 0.082 0.182
25000 50 4.881 0.226 0.455
50000 50 10.31 0.363 0.895

关于这个结论,归并排序没什么好说的,在o(n)的空间复杂度消耗下,其o(nlogn)的时间复杂度确实使它的排序速度最快,而且n(nlogn)真的比o(n^2)快太多了。然而,其中有一点令人奇怪:当n比较大,size比较小的时候,归并排序的时间甚至比不过插入排序。

我个人的想法是:

  • size越大,生成数组完全无序的可能性就越高,使得插入排序的时间复杂度接近O(n^2),导致其时间变得越来越接近冒泡排序。
  • size越小,生成数组完全有序或局部有序的可能性就越高,使得插入排序的时间复杂度接近O(n),比起归并的o(nlogn)要小,因此所用的时间比归并少。

实验代码

可直接粘贴运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
const makeRandomArr = exports.makeRandomArr = size => {
return Array(size).fill(null).map(() => Math.round(Math.random() * 1000));
};

const bubSort = exports.bubSort = arr => {
if (arr == null) return arr;
for (let round = 0; round < arr.length; round++) { // round每一轮
for (let target = 0; target < arr.length - 1 - round; target++) { //target当前比较对象
if (arr[target] > arr[target + 1])
[ arr[target], arr[target + 1] ] = [ arr[target + 1], arr[target] ];
}
}
}

const insSort = exports.insSort = arr => {
if (arr == null) return arr;
for(let nextSort = 1; nextSort < arr.length; nextSort++) {
for (let sorted = nextSort - 1; sorted > -1; sorted--) {
if (arr[sorted + 1] < arr[sorted]) [ arr[sorted + 1], arr[sorted] ] = [ arr[sorted], arr[sorted + 1] ];
else break;
}
}
}

const mergeSort = exports.mergeSort = arr => {
const merge = (arr, l, mid, r) => {
let p1 = l;
let p2 = mid + 1;
let helpOffset = 0;
let helpArr = Array(r - l + 1);
while(p1 <= mid && p2 <= r) {
if (arr[p1] <= arr[p2]) {
helpArr[helpOffset++] = arr[p1++];
} else {
helpArr[helpOffset++] = arr[p2++];
}
}

while (p1 <= mid) {
helpArr[helpOffset++] = arr[p1++];
}

while (p2 <= r) {
helpArr[helpOffset++] = arr[p2++];
}

for (let offset = 0; offset < helpArr.length; offset++) {
arr[l + offset] = helpArr[offset];
}
}
const innerMergeSort = (arr, l, r) => {
if (l === r) return;
// console.log('l r', l, r);

const mid = Math.floor((l + r) / 2);
// console.log('mid', mid);
innerMergeSort(arr, l, mid);
innerMergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
innerMergeSort(arr, 0, arr.length - 1);
}


(function main() {

let sum = 0;
let sum2 = 0;
let sum3 = 0;

let n = 10;
let size = 1000000;

for (let i = 0; i < n; i++) {
let arr = makeRandomArr(size);
let anothrArr = arr.slice();

let t1 = new Date();
console.time('bub'+i);

bubSort(arr);

console.timeEnd('bub'+i);
let t2 = new Date()
sum += t2 - t1;

let t3 = new Date();
console.time('ins'+i);

insSort(anothrArr);

let t4 = new Date();
sum2 += t4 - t3;
console.timeEnd('ins'+i);

let t5 = new Date();
console.time('merge'+i);

mergeSort(anothrArr);

let t6 = new Date();
sum3 += t6 - t5;
console.timeEnd('merge'+i);
}
console.log(`sum: ${sum / 1000}s, sum2: ${sum2 / 1000}s, sum3: ${sum3 / 1000}s`);
})();