算法笔记(1)

记录一下最近用到的几种常见算法的优劣(冒泡排序,选择排序,插入排序,快速排序。)。下面将给出四种算法的javascript代码和对10w条数据进行排序的结果,10w条数据使用Math.random产生10w条随机整数。在对1w条一下的数据进行排序时,大多数算法都在毫秒的差距上体现不出来。
用js进行测试。
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubblingSort() {
let start = Date.now();
for (let x=0;x<this.data.length;x++) {
for (let y=x+1;y<this.data.length;y++) {
if (this.data[x]>this.data[y]) {
let tmp = this.data[x];
this.data[x] = this.data[y];
this.data[y] = tmp;
}
}
}
// console.log("paoSort:",this.data.toString());
console.log("paoSort time: ",Date.now() - start);
}
冒泡排序对10w条数据排序的时间(结果都是进行反复测试的,随机选择一条):
paoSort time: 15727 (毫秒)
选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function selectSort() {
let start = Date.now();
for (let x=0;x<this.data.length-1;x++) {
let min = x;
for (let y=x+1;y<this.data.length;y++) {
if (this.data[min]>this.data[y]) {
min = y;
}
}
if (x !== min) {
let tmp = this.data[x];
this.data[x] = this.data[min];
this.data[min] = tmp;
}
}
// console.log("selectSort:",this.data.toString());
console.log("selectSort time: ",Date.now() - start);
}
选择排序对10w条数据排序消耗的大致时间是:
selectSort time: 6359(毫秒)
可以看到,10w条数据排序适,选择排序明显优于冒泡排序
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertSort() {
let start = Date.now();
for (let x=1;x<this.data.length;x++) {
if (this.data[x] < this.data[x-1]) {
let tmp = this.data[x];
for (let y=x;y>=0;y--) {
if (y>0 && this.data[y-1]>tmp) {
this.data[y] = this.data[y-1];
} else {
this.data[y] = tmp;
break;
}
}
}
}
// console.log("insert÷Sort:",this.data.toString());
console.log("insertSort time: ",Date.now() - start);
}
插入排序对10w条数据进行排序消耗的时间:
insertSort time: 3246(毫秒)
可以看到,插入排序的性能又要明显高于冒泡和选择。
快速排序
1
2
3
4
5
6
7
8
9
function fastSortFunc(data) {
if (data.length <= 1) return data;
let left =[],right = [];
let sign = data[0];
for (let x=1;x<data.length;x++) {
data[x] <= sign ? left.push(data[x]) : right.push(data[x]);
}
return this.fastSortFunc(left).concat(sign,this.fastSortFunc(right));
}
快速排序对10w条进行排序的消耗时间:
fastSort time 74(毫秒)
可以看到快速排序的性能远高于前面的三种算法。实际上,快速算法在算法学中属于高级算法的一种。前面三种算法属于基本算法。

  • 算法测试代码
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
function TestArr(len) {
this.data = new Array(len);
for (let i=0;i<len;i++) {
this.data[i] = Math.floor(Math.random()*len+1);
// this.data = i;
}
// console.log("init data:",this.data.toString());

this.paoSort = function () {
let start = Date.now();
let num = 0;
for (let x=0;x<this.data.length;x++) {
for (let y=x+1;y<this.data.length;y++) {
num++;
if (this.data[x]>this.data[y]) {
let tmp = this.data[x];
this.data[x] = this.data[y];
this.data[y] = tmp;
}
}
}
console.log("num:",num);
// console.log("paoSort:",this.data.toString());
console.log("paoSort time: ",Date.now() - start);
}
this.selectSort = function () {
let start = Date.now();
let num = 0;
for (let x=0;x<this.data.length-1;x++) {
let min = x;
for (let y=x+1;y<this.data.length;y++) {
num++;
if (this.data[min]>this.data[y]) {
min = y;
}
}
if (x !== min) {
let tmp = this.data[x];
this.data[x] = this.data[min];
this.data[min] = tmp;
}
}
console.log("num:",num);
// console.log("selectSort:",this.data.toString());
console.log("selectSort time: ",Date.now() - start);
}

this.insertSort = function() {
let start = Date.now();
for (let x=1;x<this.data.length;x++) {
if (this.data[x] < this.data[x-1]) {
let tmp = this.data[x];
for (let y=x;y>=0;y--) {
if (y>0 && this.data[y-1]>tmp) {
this.data[y] = this.data[y-1];
} else {
this.data[y] = tmp;
break;
}
}
}
}
// console.log("insert÷Sort:",this.data.toString());
console.log("insertSort time: ",Date.now() - start);
}

this.fastSortFunc = function (data) {
if (data.length <= 1) return data;
let left =[],right = [];
let sign = data[0];
for (let x=1;x<data.length;x++) {
data[x] <= sign ? left.push(data[x]) : right.push(data[x]);
}
return this.fastSortFunc(left).concat(sign,this.fastSortFunc(right));
}

this.fastSort = function () {
let start = Date.now();
this.data = this.fastSortFunc(this.data);
console.log("fastSort time",Date.now()-start);
// console.log("fastSort:",this.data);
}


}
let a = new TestArr(100000);
// a.paoSort();
// a.selectSort()
// a.insertSort();
a.fastSort();
作者

itpika

发布于

2019-11-30 21:54:46

更新于

2021-01-18 14:13:32

许可协议

评论