前言

有是一篇面经，今天面经不同于以往。这次的内容是算法。虽说我们日常开发用到算法的场景并不多，但是作为面试这是一道永远都要跨过去的槛。

开始算法之前，贴上之前《面经》系列的文章：

“金三银四”，让我们愉快的开始准备Web面经吧：CSS篇

元宵节，猿宵节，写代码之余面经走一波：JavaScript篇

中高端Web前端面试题，直击BAT：JavaScript篇

“金三银四”，让我们愉快的开始准备Web面经吧：JavaScript-上

冲击BAT，寒冬逆袭必备面经：Vue必问题目

正文

一般来说时间/空间复杂度是必问的内容，所以先贴一个常用表：

常考排序

冒泡：
function bubbleSort(arr) {
 let len = arr.length;
 for (let i = 0; i < len; i++) {
 for (let j = 0; j < len - 1 - i; j++) {
 if (arr[j] > arr[j+1]) { 
 [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
 }
 }
 }
 return arr;
}

没啥好解释的了吧？

快排:

function quickSort(arr, left, right) {
 let len = arr.length;
 let partitionIndex;
 left = typeof left !== 'number' ? 0 : left;
 right = typeof right !== 'number' ? len - 1 : right;
 if (left < right) {
 partitionIndex = partition(arr, left, right);
 quickSort(arr, left, partitionIndex - 1);
 quickSort(arr, partitionIndex + 1, right);
 }
 return arr;
}
function partition(arr, left, right) { 
 let pivot = left; 
 let index = pivot + 1;
 for (let i = index; i <= right; i++) {
 if (arr[i] < arr[pivot]) {
 [arr[i], arr[index]] = [arr[index], arr[i]];
 index++;
 }
 }
 [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
 return index - 1;
}

选择排序:

function selectionSort(arr) {
	let len = arr.length;
	let minIndex;
	for (let i = 0; i < len - 1; i++) {
		minIndex = i;
		for (let j = i + 1; j < len; j++) {
			if (arr[j] < arr[minIndex]) { 
			 minIndex = j; 
		 }
		}
		[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
	}
return arr;
}

插入排序：

function insertionSort(arr) {
	let len = arr.length;
	let preIndex, current;
	for (let i = 1; i < len; 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;
}

归并排序:

function mergeSort(arr) { 
 let len = arr.length;
 if(len < 2) {
 return arr;
 }
 let middle = Math.floor(len / 2),
 left = arr.slice(0, middle),
 right = arr.slice(middle);
 return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
 let result = [];
 while (left.length && right.length) {
 if (left[0] <= right[0]) {
 result.push(left.shift());
 } else {
 result.push(right.shift());
 }
 }
 result.push(...left);
 result.push(...right);
 return result;
}

堆排序：

var len; 
function buildMaxHeap(arr) { 
 len = arr.length;
 for (let i = Math.floor(len / 2); i >= 0; i--) {
 heapify(arr, i);
 }
}
function heapify(arr, i) { 
 let left = 2 * i + 1;
 let right = 2 * i + 2;
 let largest = i;
 if (left < len && arr[left] > arr[largest]) {
 largest = left;
 }
 if (right < len && arr[right] > arr[largest]) {
 largest = right;
 }
 if (largest !== i) {
 [arr[i], arr[largest]] = [arr[largest], arr[i]];
 heapify(arr, largest);
 }
}
function heapSort(arr) {
 buildMaxHeap(arr);
 for (let i = arr.length - 1; i > 0; i--) {
 [arr[0],arr[i]]=[arr[i],arr[0]];
 len--;
 heapify(arr, 0);
 }
 return arr;
}

尾声

这次总结的是一些排序的代码逻辑，如果有必要的话，下一篇来一些二叉树之类的。希望可以给大家带来帮助吧~