lanbos'blog

js的简单算法

js是弱类型语言,不太适合研究算法和数据结构,这里只是研究一下粗浅的算法,也是对算法入门书籍《啊哈,算法》的一点读书笔记。

冒泡排序

冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换 过来。如果有N个需要排序的数字的话,需要循环(N-1)*(N-1)次,排序的复杂程度是O(N²);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// js冒泡排序
var testArry=[8,100,29,1,888,15,1,6,33];
function makeRight(testArry){
var aLen=testArry.length;
var a=[];
var midKey=null;
for (var i=0;i<aLen;i++){
a.push(testArry[i]);
}
for (var j=0;j<aLen-1;j++){
for (var k=0;k<aLen-1;k++){
if(a[k]<a[k+1]){
midKey=a[k];
a[k]=a[k+1];
a[k+1]=midKey;
}
}
}
console.log(a);
}
makeRight(testArry);

快速排序

“快速排序”的思想很简单,整个排序过程只需要三步:
1.在数据集之中,选择一个元素作为”基准”(pivot)。
2.所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
3.对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var testArry=[8,100,29,1,888,15,1,6,33];
var quickSort=function(arr){
if(arr.length<=1){return arr;}
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[];
var right=[];
for (var i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot],quickSort(right));
};
quickSort(testArry);

(参考自阮一峰的《快速排序(Quicksort)的Javascript实现》)

排序去重

利用之前的快速排序,循环快速排序生成的数组,每两个对比然后把不一样的放进一个新的数组中返回

1
2
3
4
5
6
7
8
9
10
var noRepeat = function(arr) {
var sortArry=quickSort(arr);
var results=[];
for(var i=0;i<sortArry.length;i++){
if(sortArry[i]!=sortArry[i+1]){
results.push(sortArry[i]);
}
}
return results;
}