11. 各种排序
// 插入排序function insertSort(arr) { var temp for (var i = 1; i < arr.length; i++) { temp = arr[i] for (var j = i; j > 0 && temp < arr[j - 1]; j--) { arr[j] = arr[j - 1] } arr[j] = temp } return arr } console.log(insertSort([3, 1, 8, 2, 5])) // 归并排序function mergeSort(array) { var result = array.slice(0) function sort(array) { var length = array.length var mid = Math.floor(length * 0.5) var left = array.slice(0, mid) var right = array.slice(mid, length) if (length === 1) return array return merge(sort(left), sort(right)) } function merge(left, right) { var result = [] while (left.length || right.length) { if (left.length && right.length) { if (left[0] < right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } else if (left.length) { result.push(left.shift()) } else { result.push(right.shift()) } } return result } return sort(result) } console.log(mergeSort([5, 2, 8, 3, 6])) // 二分插入排序function twoSort(array) { var len = array.length, i, j, tmp, low, high, mid, result result = array.slice(0) for (i = 1; i < len; i++) { tmp = result[i] low = 0 high = i - 1 while (low <= high) { mid = parseInt((high + low) / 2, 10) if (tmp < result[mid]) { high = mid - 1 } else { low = mid + 1 } } for (j = i - 1; j >= high + 1; j--) { result[j + 1] = result[j] } result[j + 1] = tmp } return result } console.log(twoSort([4, 1, 7, 2, 5]))12. 使用尾递归对斐波那契优化
递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。
// 传统递归斐波那契, 会造成超时或溢出function Fibonacci (n) { if ( n <= 1 ) {return 1}; return Fibonacci(n - 1) + Fibonacci(n - 2);} Fibonacci(10) // 89Fibonacci(100) // 超时Fibonacci(500) // 超时 // 使用尾递归优化, 可规避风险function Fibonacci2 (n , ac1 = 1 , ac2 = 1) { if( n <= 1 ) {return ac2}; return Fibonacci2 (n - 1, ac2, ac1 + ac2);} Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208Fibonacci2(10000) // Infinity13. 两个升序数组合并为一个升序数组
function sort (A, B) { var i = 0, j = 0, p = 0, m = A.length, n = B.length, C = [] while (i < m || j < n) { if (i < m && j < n) { C[p++] = A[i] < B[j] ? A[i++] : B[j++] } else if (i < m) { C[p++] = A[i++] } else { C[p++] = B[j++] } } return C}