简单算法简单算法

斐波那契数列斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1, F(N) = F(N - 1) + F(N - 2), 其中 N > 1，给定 N，计算 F(N)。

function fib(N) { // 若 N <= 1，则返回 N if (N <= 1) { return N; } // 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1 if (N == 2) { return 1; } // 至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。 let current = 0; // 代表 fib(N) let prev1 = 1; // 代表fib(N-1) let prev2 = 1; // 代表 fib(N-2)for (let i = 3; i <= N; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return current; }

时间复杂度：O(N)。
空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。
冒泡排序基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
每一趟遍历，将一个最大的数移到序列末尾（比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换）。

文章图片

function bubbleSort(arr) { if (!arr || !arr.length) { return [] } // 外部的循环控制所有回合 for (let i = 0; i < arr.length - 1; i++) { // 内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换 for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j+1]) { const temp = arr[j+1] arr[j+1] = arr[j] arr[j] = temp } } } }

优化版本：

/* * 如果有 100 个数的数组，仅前面 10 个无序，后面 90 个都已排好序且都大于前面 10 个数字，那么在第一趟遍历后， * 最后发生交换的位置必定小于 10，且这个位置之后的数据必定已经有序了， * 记录下这个位置，第二次只要从数组头部遍历到这个位置就可以了 */ function bubbleSort(arr) { if (!arr || !arr.length) { return [] } let flag = arr.length while(flag) { let n = flag flag = 0 for (let i = 1; i < n; i++) { if (arr[i - 1] > arr[i]) { let temp = arr[i] arr[i] = arr[i - 1] arr[i - 1] = temp flag = i } } } }

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

文章图片

function insertSort(arr) { // let len = arr.length; for (let i = 1; i < arr.length; i++) { // 将 arr[i] 插入到有序队列（arr[0] —— arr[i-1]）中 for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { let temp = arr[j + 1] arr[j + 1] = arr[j] arr[j] = temp } } return arr; }

快速排序快速排序每一趟排序，都会寻找一个基准元素，有的采用第一个元素，有的会随机生成一个，但是基本思想是不变的，一趟排序结束，会形成以基准元素为分界点的两部分，其中左边比基准元素小（假设从小到大排序），右边比基准元素大。然后再以相同的方法处理左边和右边两部分，即递归。

文章图片

function quickSort(arr, left, right) { left = typeof left === 'number' ? left : 0 right = typeof right === 'number' ? right : arr.length - 1if (left < right) { const partitionIndex = partition(arr, left, right) quickSort(arr, left, partitionIndex - 1) quickSort(arr, partitionIndex + 1, right) }return arr } // 分区操作，设定基准值（pivot） 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 }

归并排序（Merge Sort）分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

文章图片

function mergeSort(arr) { const len = arr.length; if (len < 2) { return arr; } const middle = Math.floor(len / 2); const left = arr.slice(0, middle); const right = arr.slice(middle); return mergeArr(mergeSort(left), mergeSort(right)); }function mergeArr(left, right) { var result = []; 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()); }return result; }

打乱数组打乱一个没有重复元素的数组
洗牌算法：从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。

class Disorder { constructor(arr) { this.originArr = [ ...arr ] }reset() { return this.originArr }shuffle() { const shuffleArr = [ ...this.originArr ] let curLen = shuffleArr.length - 1 while (curLen > -1) { // 生成一个范围在当前下标到数组末尾元素下标之间的随机整数 const random = Math.floor(shuffleArr.length * Math.random()) console.log(random); // 将当前元素和随机选出的下标所指的元素互相交换 [ shuffleArr[curLen], shuffleArr[random] ] = [ shuffleArr[random], shuffleArr[curLen] ] curLen-- } return shuffleArr } }var obj = new Disorder([ 1, 4, 8, 9 ]) console.log(obj.shuffle()); console.log(obj.reset());

二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

function TreeDepth(pRoot) { if (!pRoot) { return 0; } let left = TreeDepth(pRoot.left); let right = TreeDepth(pRoot.right); return Math.max(left, right) + 1; }

二叉树的镜像操作给定的二叉树，将其变换为源二叉树的镜像。

function Mirror(pRoot) { if (!pRoot) { return null } let temp = pRoot.left pRoot.left = pRoot.right pRoot.left = tempMirror(pRoot.left) Mirror(pRoot.right)return pRoot }

树的子结构输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

// 比较两棵树是否相同 function compTree(root1, root2) { if (!root2) { return true } if (!root1) { return false } if (root1.val !== root2.val) { return false } return compTree(root1.left, root2.left) && compTree(root1.right, root2.right) }// 判断是否子结构 function HasSubtree(pRoot1, pRoot2) { if (!pRoot1 || !pRoot2) { return false } if (!compTree(pRoot1, pRoot2)) { return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2) } return true }

给一个嵌套对象，返回展平对象（属性为 a.b.c）

const obj = { a: 'a', b: [1, 2], c: true, d: function() { console.log('d') }, e:{ a: 'a-e', b: [1, 2, 3], c: false, d: function() { console.log('e-d') }, f:{ a: 'a-f', b: [1, 2, 4], c: true, d: function() { console.log('f-d') }, } } }function flatObj (data) { if (!data || data.constructor !== Object) { return {} } const obj = {} function flat(data, baseKey) { // for...in 会遍历原型链上所有属性，不推荐使用 Object.keys(data).forEach(key => { const value = https://www.it610.com/article/data[key]; const finalKey = baseKey ? `${baseKey}.${key}` : key; if (value.constructor === Object) { flat(value, finalKey); } else { obj[finalKey] = value; } }) return obj } return flat(data); }const data = flatObj(obj) data.d() data['e.d']() data['e.f.d']()

计算一个有序数组中，某个数字出现的次数

方法1：用两个循环，一个从头找一个从尾找，找到第一次出现的位置和最后一次出现的位置。再相减即可。

function GetNumberOfK(data, k) { var start = -1 var end = -1 for (var i = 0; i < data.length; i++) { if (data[i] == k) { start = i; break } } for (var j = data.length - 1; j > -1; j--) { if (data[j] == k) { end = j break } } if (start != -1 && end != -1) { return end - start + 1; } else { return 0 } }

方法2：
二分法，找到数字出现的第一次和最后一次。

function GetNumberOfK(data, k) { if (data.length == 0) { return 0; } var first = theFirst(data, 0, data.length - 1, k) var last = theLast(data, first - 1, data.length - 1, k) if (first != -1 && last != -1) { return last - first + 1; } else { return 0; } } // 找到第一次出现K的位置 function theFirst(data, start, end, k) { if (start > end) { return -1; } var mid = parseInt((start + end) / 2) if (data[mid] > k) { end = mid - 1; return theFirst(data, start, end, k) } else if (data[mid] < k) { start = mid + 1 return theFirst(data, start, end, k) } // 还要多加一个判断如果mid-1也为k的话，说明第一次出现的位置还更小。 else if ((mid - 1 >= 0) && (data[mid - 1] == k)) { return theFirst(data, start, mid - 1, k) } else { return mid; } } // 找到最后一次出现K的位置 function theLast(data, start, end, k) { if (start > end) { return -1; } var mid = parseInt((start + end) / 2) if (data[mid] > k) { end = mid - 1; return theLast(data, start, end, k) } else if (data[mid] < k) { start = mid + 1 return theLast(data, start, end, k) } // 还要多加一个判断如果mid+1也为k的话，说明最后一次出现的位置还更大。 else if ((mid + 1 < data.length) && (data[mid + 1] == k)) { return theLast(data, mid + 1, end, k) } else { return mid; } }

其他排序见1
【简单算法】其他排序见2
其他算法见