摘要：算法題斐波拉契數(shù)列冒泡排序好中壞改進(jìn)版初始時(shí)最后位置保持不變每趟開始時(shí)無記錄交換記錄交換的位置為下一趟排序作準(zhǔn)備選擇排序好中壞插入排序好平壞希爾排序好中壞歸并排序好平壞采用自上而下的遞歸方法快速排序好平壞

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

改進(jìn)版：

function bubbleSort2(arr) {
    var i = arr.length-1;  // 初始時(shí),最后位置保持不變
    while ( i> 0) {
        var pos= 0;  // 每趟開始時(shí),無記錄交換
        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;  //為下一趟排序作準(zhǔn)備
     }
     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

// 深度優(yōu)先遍歷
    function dfs(v) {
        this.marked[v] = true;
        for each(var w in this.adj[v]) {
            if (!this.marked[w]) {
                this.dfs(w);
            }
        }
    }

// 廣度優(yōu)先遍歷
    function bfs(s) {
        var queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加到隊(duì)尾
        while (queue.length > 0) {
            var v = queue.shift(); // 從隊(duì)首移除
            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;
    }