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

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