常见算法

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

    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;
    }