算法与数据结构JS版

发表于 |

本篇博客为记录学习《数据结构与算法JavaScript语言描述》的笔。
1、递归算法，比较常见，属于比较简单类型的。

返回数字1-5的之间的整数相乘结果

1
2
3
4
5
6
7
8
function factorial(number){
	if(number == 1){
		return 1;
	} else {
		return number * factorial(number-1);	//此算法核心在这一句
	}
}
console.log(factorial(5));	//150

reduce迭代方法同样可以实现累加（乘）效果

1
2
3
4
5
var arr = [7, 4, 122, 20, 3333];
var newArr = arr.reduce(function(a,b){
	return a+b;
});
console.log(newArr);

2、sort排序，函数中传入ab表示第一个参数和第二个参数，两者相减，返回小于0的数表示是从小到大排序

1
2
3
4
5
6
var arr = [7, 4, 122, 20, 3333];
var newArr = arr.sort(function(a,b){
	return a-b;
	return b-a;		//从大到小排序
});
console.log(newArr);

3、创建二维数组,原理是先创建外层数组元素，再对外层元素创建内层数组元素

1
2
3
4
5
6
7
8
9
10
11
12
13
Array.matrix = function(numrows, numcols, initial){
	var arr = [];
	for(var i = 0; i < numrows; i++){
		var col=[];
		for(var j = 0; j < numcols; j++){
			col[j] = initial;
		}
		arr[i] = col;
	}
	return arr;
}
var nums = Array.matrix(5,5,0);
console.log(nums)

4、求3个学生的平均成绩：

1
2
3
4
5
6
7
8
9
var grades = [[89, 77, 78], [76, 82, 81], [91,69,70]];
for(var i = 0; i < grades.length; i++){
	var col = grades[i];		
	var total = col.reduce(function(a,b){	//累加求总分
		return a+b
	});
	var pingjun = total  / col.length;
	console.log("text" + (i+1) + "成绩：" + pingjun);		
}

5、快速排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function qSort(arr){
	if(arr.length == 0){
		return [];
	}
	var left = [];
	var right = [];
	var pivot = arr[0];
	for(var i = 1; i < arr.length; i++){
		if(arr[i] < pivot){
			left.push(arr[i])
		} else {
			right.push(arr[i])
		}
	}
	return qSort(left).concat(pivot, qSort(right));
}
var a = [];
for(var i = 0; i < 100000; i++){
	a[i] = Math.floor((Math.random()*100)+1)
}

书上说这种快速排序算法对大型数据排序很快，但是我经过测试，对100000个数进行排序，花了将近1000ms,而如果用sort方法，只需要40ms左右，所以看来sort还是比这个快速排序算法好用。