算法题
斐波拉契数列
function f(n) { if (n == 0 || n == 1) { return n; } else { return f(n-1) + f(n - 2); } } 1.冒泡排序
好、中、坏：O(n)、O(n^2)、O(n^2)
function bubbleSort(arr) { var len = arr.length; var temp; for (var i = len; i >= 2; --i) { for (var j = 0; j <= i - 1; ++j) { if (arr[j] > arr[j + 1]) { 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 pos= 0; // 每趟开始时,无记录交换 for (var j= 0; j< i; j++) if (arr[j]> arr[j+1]) { pos= j; // 记录交换的位置 var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } i= pos; //为下一趟排序作准备 } return arr;} 2.选择排序
好 中 坏 ： O(n^2)、O(n^2)、O(n^2)
function selectionSort(arr) { var min, temp; var len = arr.length; for (var i = 0; i < len - 1; ++i) { min = i; for (var j = i + 1; j < len; ++j) { if (arr[j] < arr[min]) { min = j; } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } return arr;} 3.插入排序
好、平、坏：O(n^2)、O(n)、O(n^2)
function insertSort(arr) { var temp, i; var len = arr.length; for (var j = 1; j <= len - 1; ++j) { temp = arr[j]; i = j; while (i > 0 && (arr[i - 1] >= temp)) { arr[i] = arr[i - 1]; --i; } arr[i] = temp; } return arr; } 4.希尔排序
好 中 坏 ： O(n^1.3)、O(nlogn)-O(n^2)、O(n^2)
function shellsort(arr) { var len = arr.length; var h = 1; while (h < len / 3) { h = 3 * h + 1; } while (h >= 1) { for (var i = h; i < len; i++) { for (var j = i; j >= h && arr[j] < arr[j-h];j -= h) { temp = arr[j]; arr[j] = arr [j - h]; arr[j - h] = temp; } } h = (h-1)/3; } return arr;} 5.归并排序
好、平、坏：O(nlogn)、O(nlogn)、O(nlogn)
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 = []; 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;} 6.快速排序
好、平、坏：O(nlogn)、O(nlogn)、O(n^2)
function qSort(arr) { var len = arr.length; if (len == 0) { return []; } var left = []; var right = []; var flag = arr[0]; for (var i = 1; i < len; i++) { if (arr[i] < flag) { left.push(arr[i]); } else { right.push(arr[i]); } } return qSort(left).concat(flag, qSort(right)); }/// var arr = [2,1,3,4,3]; var m = qSort(arr); console.log(m); //[1, 2, 3, 3, 4] BST遍历
// 中序： function inOrder(node) { if (!(node == null)) { inOrder(node.left); putstr(node.show() + " "); inOrder(node.right); } }// 先序： function preOrder(node) { if (!(node == null)) { putstr(node.show() + " "); preOrder(node.left); preOrder(node.right); } }// 后序： function postOrder(node) { if (!(node == null)) { postOrder(node.left); postOrder(node.right); putstr(node.show() + " "); } } DFS&BFS
// 深度优先遍历 function dfs(v) { this.marked[v] = true; for each(var w in this.adj[v]) { if (!this.marked[w]) { this.dfs(w); } } }// 广度优先遍历 function bfs(s) { var queue = []; this.marked[s] = true; queue.push(s); // 添加到队尾 while (queue.length > 0) { var v = queue.shift(); // 从队首移除 if (v == undefined) { print("Visisted vertex: " + v); } for each(var w in this.adj[v]) { if (!this.marked[w]) { this.edgeTo[w] = v; this.marked[w] = true; queue.push(w); } } } } 二分搜索算法
function binSearch(arr, data) { var upperBound = arr.length-1; var lowerBound = 0; while (lowerBound <= upperBound) { var mid = Math.floor((upperBound + lowerBound) / 2); if (arr[mid] < data) { lowerBound = mid + 1; } else if (arr[mid] > data) { upperBound = mid - 1; } else { return mid; } } return -1; }