Awebone's Blog

数据结构与算法JavaScript学习(三)

数据结构与算法JavaScript学习(三)

搜索算法

顺序或线性搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function ArrayList(){
var array=[];
this.insert=function(item){
array.push(item);
};
this.toString=function(){
return array.join();
};
//顺序搜索
this.sequentialSearch=function (item) {
for (var i = 0; i < array.length; i++) {
if (item===array[i]) {
return i;
}
}
return -1;
};
}

二分搜索

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
function ArrayList(){
var array=[];
this.insert=function(item){
array.push(item);
};
this.toString=function(){
return array.join();
};
//快速排序:分治递归
this.quickSort=function () {
quick(array,0,array.length-1);
};
//快排
var quick=function (array,left,right) {
var index;
if (array.length>1) {
index=partition(array,left,right);
if (left<index-1) {
quick(array,left,index-1);
}
if (index<right) {
quick(array,index,right);
}
}
};
//划分过程
var partition=function(array,left,right){
var pivot=array[Math.floor((right+left)/2)],i=left,j=right;//选主元
while (i<=j) {
while (array[i]<pivot) {
i++;
}
while (array[j]>pivot) {
j--;
}
if (i<=j) {
swapQuickStort(array,i,j);
i++;
j--;
}
}
return i;
};
//交换数组元素
var swapQuickStort=function (array,index1,index2) {
var aux=array[index1];
array[index1]=array[index2];
array[index2]=aux;
};
//二分搜索
this.binarySearch=function (item) {
this.quickSort();//快速排序
var low=0,high=array.length-1,mid,element;
while (low<=high) {
mid=Math.floor((low+high)/2);
element=array[mid];
if (element<item) {
low=mid+1;
}else if (element>item) {
high=mid-1;
}else {
return mid;
}
}
return -1;
};
}