常见算法

摘要：算法题斐波拉契数列冒泡排序好中坏改进版初始时最后位置保持不变每趟开始时无记录交换记录交换的位置为下一趟排序作准备选择排序好中坏插入排序好平坏希尔排序好中坏归并排序好平坏采用自上而下的递归方法快速排序好平坏

</>复制代码 
    function  f(n) {
        if (n == 0 || n == 1) {
            return n;
        }
        else {
            return f(n-1) + f(n - 2);
        }
    }

好、中、坏：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;
}

好 中 坏 ： 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;
}

好、平、坏：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;
    }

好 中 坏 ： 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;
}

好、平、坏：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;
}

好、平、坏：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]

</>复制代码 
// 中序：
    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;
    }