前端常用算法梳理

[hsipeng]

算法

如何分析时间复杂度

时间复杂度量级

• 常数阶 O(1) 赋值语句
• 线性阶 O(n) 线性查找
• 对数阶 O(logn) 二分查找
• 线性对数阶 O(nlogn) 归并排序
• 平方阶 O(n2) 冒泡排序
• 指数阶 O(2n)
• 阶乘阶 O(n!)

冒泡排序

比较相邻，依次交换

function bubbleSort(arr){
	var len = arr.length;
	for( var i =0; i < len; i++){
		for(var j =0; j<len -1; j++) {
			if(arr[j] > arr[j+1]){
				var temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = temp;
			}		
		}
	
	}
	return arr;
}

改进版，正向同时反向冒泡

function bubbleSort3(arr){
	var low = 0;
	var high = arr.length -1;
	var tmp, j;
	console.time('改进后冒泡排序耗时');
	while(low < high){
		for(j=low; j< high; ++j){
			if(arr[j] > arr[j+1]){
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
		--high;
		for(j=high; j>low; --j){
			if(arr[j] < arr[j-1]){
				tmp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = tmp;
			}
		}
		++low;
	
	}
	console.End('改进后冒泡排序耗时');
}

希尔排序

指定间隔直接插入排序

function shellSort(arr){
	var len = arr.length,
		temp,
		gap = 1;
	console.time('希尔排序耗时:');
	while(gap < len/5){
		gap = gap *5 +1;
	}

	for(gap; gap >0; gap = Math.floor(gap/5)){
		for(var i = gap; i< len; i++){
			temp = arr[i];
			for(var j = i -gap; j >= 0 && arr[j] > temp; j -=gap){
			arr[j+gap] = arr[j];
		}
			arr[j+gap] = temp;
		}
	}
	console.End('希尔排序耗时:');
	return arr;
}

归并排序

采用分治算法

function mergeSort(arr){
	var len = arr.length;
	if(len < 2) {
		return arr;
	}
	var middle = Math.floor(len/2),
		left = arr.slice(0, middle),
		right = arr.slice(middle);
	return merge(mergeSort(left),mergeSort(right));
}

function merge(left, right){
	var result = [];
	console.time("归并排序耗时:");
	while(left.length&&right.length){
		if(left[0] <= right[0]){
			result.push(left.shift());
		}else{
			result.push(right.shift());
		}
	}

	while(left.length){
		result.push(left.shift());
	}

	while(right.length){
		result.push(right.shift());
	}

	console.End("归并排序耗时:");
  return result;
}

快速排序

分组排序,较小值，较大值

const quickSort = (function(){
	function compare(a, b){
		if(a === b){
			return 0;
		}

		return a  < b ? -1 : 1;
	}

	function swap(array, a, b){
		[array[a], array[b]] = [array[b], array[a]];
	}

	// 分治函数
	function partition(array, left, right){
		// 用index 取中间值而非splic
		const pivot = array[Math.floor(right + left)/2)]
		let i = left;
		let j = right;
		while(i <= j){
			while(compare(array[i], pivot) === -1){
				i++;
			}
			while(compare(array[j], pivot) === 1){
				j--;
			}

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

	// 快排

	function quick(array, left, right){
		let index;
		if(array.length > 1){
			index = partition(array, left, right);
			if(left < index -1){
				quick(array, left, index -1)
			}

			if(index < right){
				quick(array, index, right)
			}
		}
		return array
	}

	return function quickSort(array){
		return quick(array, 0,array.length -1);
	}
})	

查找算法

二分查找法

折半查找，要求线性结构和有序

function binarySearch(arr, target){
	let max = arr.length -1;
	let min = 0;
	while(min <= max){
		let mid = Math.floor((max + min)/2)
		if(target < arr[mid]){
			max = mid -1;
		}else if (target > arr[mid]){
			min = mid + 1;
		} else {
			return mid;
		}
	}
	return -1;
}

线性查找

遍历

const linearSearch = (arr, target) => {
		for(let i = 0; i< arr.length; i++){
		if(arr[i]=== target){
			return i;
		}
	}

	return -1;
	
}