摘录js部分算法

发表于   |   分类于   |     |   阅读次数

问题一例

如何在数组中间位置添加数组？

题目很简单，无非是找到数组中间位置然后把新数组插入即可；比较容易的想到下面这段

1
2
3
4
5
6
function Add(arr, newArr){
    arr.splice(Math.floor(arr.length / 2), 0, newArr)
    return arr;
}
Add([1,2,3,4,5,6,7], [8,9,10])

但是实际操作后可能会发现，结果是这样的

1
> (8) [1, 2, 3, Array(3), 4, 5, 6, 7]

(- -)!、但是这并不是我们想要的

我们需要的是一个纯数组，是的它有问题！
其实思路肯定是没有错的，仅需要利用一个技巧就行了，就是 apply 或者 call 的特性来改造一下

1
2
3
4
5
6
function Add(arr, newArr){
    arr.splice.apply(arr, [Math.floor(arr.length / 2), 0].concat(newArr))
    return arr;
}
Add([1,2,3,4,5,6,7], [8,9,10])

来看下结果

1
> (10) [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]

算法之排序

前面的只是一个开头菜，引导大家一些思路，哈哈
下面来看一些算法用js的实现，详细内容请跟随链接跳转至wiki了解，觉得wiki已经很清晰了，有图片的表现的更直观一些；实在不明白的手写几遍也能差不多理解了；
可能实际使用中并没有太多的算法需要常用，但是掌握一些思想还是比较重要的；比如前两个~

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Array.prototype.bubble_sort = function() {
	var i, j, temp;
	for (i = 0; i < this.length - 1; i++)
		for (j = 0; j < this.length - 1 - i; j++)
			if (this[j] > this[j + 1]) {
				temp = this[j];
				this[j] = this[j + 1];
				this[j + 1] = temp;
			}
	return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();
console.info(num);

摘自wiki百科

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Array.prototype.quick_sort = function() {
	var len = this.length;
	if (len <= 1)
		return this.slice(0);
	var left = [];
	var right = [];
	var mid = [this[0]];
	for (var i = 1; i < len; i++)
		if (this[i] < mid[0])
			left.push(this[i]);
		else
			right.push(this[i]);
	return left.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();

摘自wiki百科

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Array.prototype.selection_sort = function() {
	var i, j, min;
	var temp;
	for (i = 0; i < this.length - 1; i++) {
		min = i;
		for (j = i + 1; j < this.length; j++)
			if (this[min] > this[j])
				min = j;
		temp = this[min];
		this[min] = this[i];
		this[i] = temp;
	}
	return this;
};

摘自wiki百科

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
Array.prototype.insertion_sort = function() 
 2 {
 3   var i,j;
 4   for(i = 1;i < this.length; i++){
 5     for(j = 0;j<i;j++){
 6       if(this[j]>this[i]){
 7         this.splice(j,0,this[i]);
 8         this.splice(i+1,1);
 9       }
10     }
11   }
12   return this;
13 };

摘自wiki百科

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
Array.prototype.shell_sort = function() {
	var gap, i, j;
	var temp;
	for (gap = this.length >> 1; gap > 0; gap >>= 1)
		for (i = gap; i < this.length; i++) {
			temp = this[i];
			for (j = i - gap; j >= 0 && this[j] > temp; j -= gap)
				this[j + gap] = this[j];
			this[j + gap] = temp;
		}
	return this
};

摘自wiki百科