今日算法小练习，排序与查找

发表于 | 分类于 |

从小做起，以后每天定时写几个js算法，并且做总结打卡。今天写了几个简单的排序和查找，还买了一本书，《算法导论》，接下来的2个月的目标就是它啦，加油。

快速排序

快速排序的思想是分治，比如这里[3,4,1,5,6,9]这样一个数组，先选一个轴，比如说是起点，然后先从右向左找到比这个轴小的数，并把这个小数覆盖掉轴的位置。这时候原来小数的位置可以当成是空，然后再以轴为中心从左往右找，找到比轴大的数，再把这个数覆盖原来轴所在的位置。算法复杂度最差是$$n^2$$，最好是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
function quickSort (arr,l,r) {
	var left = l,right = r;
	var key = arr[l];
	if(left < right){
		while(left < right){
			while(left<right && key < arr[right]){
				right--;
			}
			arr[left] = arr[right];
			while(left<right && key > arr[left]){
				left++;
			}
			arr[right] = arr[left];
		}
		arr[right] = arr[left];
		quickSort(arr,l,left-1);
		quickSort(arr,r+1,right);
	}			
}

var arr = [3,4,1,5,6,9];
quickSort(arr,0,5);

console.log(arr);

两种数组去重方法

第一种利用indexOf,直接每次在新数组里查找是否有值，如果有则不push进入。否则push进入。

1
2
3
4
5
6
7
8
9
10
11
function unique (arr) {
	var newArr = [];
	for(var i = 0;i<arr.length;i++){
		if(newArr.indexOf(arr[i]) == -1){
			newArr.push(arr[i]);
		}
	}
	return newArr;
}
var arr = [3,2,5,6,7,6,7,2];
console.log(unique(arr));

第二种利用hash，来生成一个键值对，用来存储已经有了的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function unique (arr){
	var newArr = [];
	var hash = {};

	for(var i = 0;i<arr.length;i++){
		if(!hash[arr[i]]){
			newArr.push(arr[i]);
			hash[arr[i]] = true;
		}
	}
	return newArr;
}
var arr = [3,2,5,6,7,6,7,2];
console.log(unique(arr));

二分查找

二分查找没什么说的，就是3个指针，分别每次从一半来查找，前提是数组已经排号序。logn是其算法时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bSearch (arr,n,left,right){		
	var mid;

	while(left<=right){
		mid = parseInt((left+right)/2);
		if(n == arr[mid]){
			return mid;
		}else if(arr[mid]<n){
			left = mid + 1;
		}else if(arr[mid]>n){
			right = mid - 1;
		}
	}
	return 0;
}

var arr = [0,3,5,7,11,14];

var x = bSearch(arr,5,0,5);
console.log(x);