一些js基础算法

发表于 | 分类于 |

前言

长时间没有接触算法,脑子生锈,写下一些常见的排序、查找算法记在博客上给自己看,代码没有写注释。

排序

1
var array = [32, 80, 1, 13, 7, 36, 49, 2, 33, 20, 55]

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
function bubbleSort(arr) {
	var l = arr.length;
	for (var i = 0; i < l; i++) {
		for (var j = 0; j < l - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				var temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr
}
function bubbleSort2(arr) {
	var i = arr.length - 1;
	while (i > 0) {
		var position = 0;
		for (var j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				position = j;
				var temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		i = position;
	}
	return arr
}
console.log(bubbleSort(array))
console.log(bubbleSort2(array))

2. 选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
	var l = arr.length, minIndex, temp;
	for (var i = 0; i < l - 1; i++) {
		minIndex = i;
		for (var j = i + 1; j < l; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	return arr
}
console.log(selectionSort(array))

3. 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
	var l = arr.length, preIndex, current;
	for (var i = 0; i < l; i++) {
		preIndex = i - 1;
		current = arr[i];
		while (preIndex >= 0 && arr[preIndex] > current) {
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = current;
	}
	return arr
}
console.log(insertionSort(array))

4. 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function mergeSort(arr){
	function _merge(left,right){
		var res = [],l_i = 0, r_i = 0
		while(l_i<left.length && r_i<right.length){
			if(left[l_i]<right[r_i]){
				res.push(left[l_i++])
			} else {
				res.push(right[r_i++])
			}
		}
		return res.concat(left.slice(l_i),right.slice(r_i))
	}
	function _ms(a){
		if(a.length < 2) return a
		var pivotIndex = Math.floor(a.length/2)
		var left = a.slice(0,pivotIndex)
		var right = a.slice(pivotIndex)
		return _merge(_ms(left),_ms(right))
	}
	return _ms(arr)
}

console.log(mergeSort(array))

5. 快速排序

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
// Nicholas C. Zakas 实现 in-place 不借助额外数组,节省空间
//https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}
function partition(items, left, right) {

    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;


    while (i <= j) {

        while (items[i] < pivot) {
            i++;
        }

        while (items[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }

    return i;
}
function quickSort(items, left, right) {

    var index;

    if (items.length > 1) {

        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;

        index = partition(items, left, right);
		console.log(index,items[index],items)

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }

    }

    return items;
}

5. 堆排序

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
function heapSort(arr) {
	var l
	// 创建大顶堆
	function _buildMaxHeap(arr) {
		l = arr.length
		for (var i = Math.floor(l / 2); i >= 0; i--) {
			_heapify(arr, i)
		}
	}

	// 调整堆
	function _heapify(arr, i) {
		var left = 2 * i + 1,
			right = 2 * i + 2,
			max = i
		if (left < l && arr[left] > arr[max]) {
			max = left
		}
		if (right < l && arr[right] > arr[max]) {
			max = right
		}

		if (max != i) {
			var temp = arr[i]
			arr[i] = arr[max]
			arr[max] = temp

			_heapify(arr, max)
		}
	}

	_buildMaxHeap(arr)

	for (var i = arr.length - 1; i > 0; i--) {
		var temp = arr[0]
		arr[0] = arr[i]
		arr[i] = temp
		l--
		_heapify(arr, 0)
	}
	return arr
}

console.log(heapSort(array))

查找

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
//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
function binarySearch(items, value){

	var startIndex  = 0,
		stopIndex   = items.length - 1,
		middle      = Math.floor((stopIndex + startIndex)/2);

	while(items[middle] != value && startIndex < stopIndex){

		//adjust search area
		if (value < items[middle]){
			stopIndex = middle - 1;
		} else if (value > items[middle]){
			startIndex = middle + 1;
		}

		//recalculate middle
		middle = Math.floor((stopIndex + startIndex)/2);
	}

	//make sure it's the right value
	return (items[middle] != value) ? -1 : middle;
}

2. 最大子串

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
function getMaxSub(s1, s2) {
	var max = 0, retchars = [];
	for(var index = 0; index < s1.length; index++){
		var count = 0, chars = []; // 每次遍历都置空
		for(var i = index, j = 0; j < s2.length; j++){
			var s1char = s1[i];
			var s2char = s2[j];
			if(s1char === s2char){
				count++;
				i++;
				chars.push(s1char);
			} else if(count) { // 如果不相同且有相同过则count和chars置空，i复位，j回退一位
				j--;
				count = 0;
				chars = [];
				i = index;
			}
			if(count > max) {
				max = count;
				retchars = chars.slice();
			}
		}
	}
	return retchars.join('');
}

getMaxSub('abcde','rodcdpp')

3. 二维数组查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var findTarget = function (target, arr) {
	console.log(arr)
	var l = arr.length,
		i = l - 1,
		j = 0
	while (i >= 0 && arr[i][j]) {
		if (arr[i][j] < target) {
			j++
		}
		else if(arr[i][j] > target) {
			i--
		} else {
			console.log(i,j)
			return true
		}
		return false
	}
}

var dda = [[1, 2, 4, 6], [2, 4, 7, 8], [8, 9, 10, 11], [9, 12, 13, 15]]
console.log(findTarget(19, dda))

杂七杂八

字符串转数字

1
2
3
4
5
6
function atoi(n) {
	return n.split("").reduce((prev, curr, index) => {
		console.log(prev,curr)
		return prev * 10 + (curr - '0')
	}, 0)
}

洗牌

1
2
3
4
5
6
7
8
9
10
function shuffleFn(a) {
    let b = []
    for(var i = a.length;i>0;){
        var index = Math.floor(Math.random() * i);
        b.push(a[index])
        a[index] = a[--i]
    }
    return b
}
shuffleFn([12,53,21,6,33,332,422,987,343645,2])

斐波那契尾递归和缓存版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 尾递归
function fibonacci(n, ac1 = 1, ac2 = 1) {
    if (n <= 1) {
        return ac1;
    }
    return fibonacci(n - 1, ac2, ac1 + ac2);
}
// cache
var fib_cache = function () {
    var cache = [1, 1];
    return function (n) {
        if (n >= cache.length) {
            for (var i = cache.length; i < n; i++) {
                cache[i] = cache[i - 1] + cache[i - 2];
            }
        }
        return cache[n - 1];
    }
}()

数组去重

1
2
3
4
5
6
7
8
9
10
Array.prototype.unique = Array.prototype.unique || function () {
            var hash = {}, res = [];
            for (var i = 0, l = this.length; i < l; i++) {
                if (!hash.hasOwnProperty(this[i])) {
                    hash[this[i]] = true;
                    res.push(this[i]);
                }
            }
            return res;
        }

数组取交集

1
2
3
4
5
6
7
8
9
10
11
12
Array.prototype.intersect = Array.prototype.intersect || function (arr) {
	   var hash = {}, res = [], i, v;
	   for (i = 0; i < arr.length; i++) {
		   hash[arr[i]] = true;
	   }
	   for (i = 0; i < this.length; i++) {
		   v = this[i];
		   if (v in hash)
			   res.push(v);
	   }
	   return res;
   }

开方

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

function sqrt(n) {
	if (n < 0) return NaN;
	if (n === 0 || n === 1) return n
	var low = 0,
		high = n,
		pivot = (low + high) / 2,
		lastPivot = pivot;
	do {
		if (Math.pow(pivot, 2) > n) {
			high = pivot
		} else if (Math.pow(pivot, 2) < n) {
			low = pivot
		} else {
			return pivot;
		}
		lastPivot = pivot
		pivot = (low + high) / 2
	}
	while (Math.abs(pivot - lastPivot) >= Number.EPSILON)
	return pivot
}

function sqrt_newton(n) {
	if (n < 0) return NaN;
	if (n === 0 || n === 1) return n
	var val = n,
		last;
	do {
		last = val;
		val = (val + n / val) / 2;
	}
	while (Math.abs(val - last) >= Number.EPSILON)
	return val
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
function fastPow(x,n) {
	if(n < 0){
		return 1/fastPow(x,Math.abs(n));
	}
	if(n === 0) return 1;
	else if(n % 2 === 1){
		return fastPow(x,n-1) * x;
	}else{
		var r = fastPow(x,n/2);
		return r * r;
	}
}