JavaScript實現排序演算法

排序演算法主要用在元素的數組排序，常見的排序演算法有冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸併排序等。這些排序演算法都可以用JavaScript實現。下麵的排序演算法都假設是從小到大進行排序，從大到小可以相應進行轉化。

冒泡排序

冒泡排序的基本思想是從頭遍歷要排序的數組，比較相鄰兩個數，如果前面位置的數大於後面位置的數，那麼就將兩者進行交換，否則不做任何操作。遍歷完一次之後，最大的數就放到了數組最後的位置。然後再從頭遍曆數組，進行同樣的操作，就可以將第二大的數放到倒數第二個位置，依此進行下去，直到所有數都排好位置為止。冒泡排序的代碼實現如下：

functon bubbleSort(arr) {
    for (var i = 0; i < arr.length-1; i++) {
        for (var j = 0; j < arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                // 交換位置
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        return arr;
    }
}

冒泡排序平均時間複雜度為O(n^2),而且是一種穩定的排序演算法。

選擇排序

選擇排序的基本思想是先找到數組中最小的元素，將它和數組的第一個元素交換位置，再找到數組中第二小的元素，將它和數組的第二個元素交換位置，依次進行下去，直到整個數組排好序為止。選擇排序代碼實現如下：

functon selectSort(arr) {
    for (var i = 0; i < arr.length-1; i++) {
        var min = arr[i];
        for (var j = i+1; j < len; j++) {
            if (arr[j] < min) {
                var temp = min;
                min = arr[j];
                arr[j] = temp;
            }
            arr[i] = min;
        }
    }
    return arr;
}

選擇排序的時間複雜度為O(n^2),而且是一個不穩定的排序演算法。

插入排序

插入排序的基本思想是將一個記錄（數）插入到已排好序的有序數列中的適當位置。插入排序的代碼實現如下：

function insertSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var key = arr[i];
        for (var j = i-1; j >= 0; j--) {
            if (arr[j] > key) {
                arr[j + 1] = arr[j];
            } else {
                arr[j + 1] = key;
            }
        }
    }
    return arr;
}

插入排序的時間複雜度為O(n^2),而且是一個穩定的排序演算法。

希爾排序

希爾排序又稱“縮小增量排序”，是在直接插入排序演算法上進行改進的，它的基本思想是先將整個待排序序列分割成若幹子序列，分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序。因為插入排序在對幾乎已經排好序的數據操作時，效率高。
希爾排序的步驟是：首先取一個小於序列長度的整數d1作為增量，對序列從頭開始把所有距離為d的元素放在同一個分組中，現在各組內進行直接插入排序；然後去第二個增量d2（小於d1），進行同樣的操作，直到增量為1，即對已經基本有序的序列進行插入排序。希爾排序代碼實現如下：

function shellSort(arr, dk) {
    for (var d = dk/2; d > 0; d /= 2) {
        for (var j = d; j < n; j++) {
            if (arr[j] < arr[j-d]) {
                var temp = arr[j];
                var k = j - d;
                while (k >= 0 && arr[k] > temp) {
                    arr[k + d] = arr[k];
                    k -= d;
                }
                arr[k + d] = temp;
            }
        }
    }
}

希爾排序的時間複雜度為O(n^3/2),而且是一個不穩定的排序演算法。

快速排序

快速排序是一種分而治之的演算法，它是冒泡排序的改進，基本思想是通過一趟排序將待排序列分割成獨立的兩部分，其中一部分的值都要比另一部分的值小，再分別對這兩部分繼續進行排序，直到整個序列有序。
快速排序的步驟是：首先從序列中選擇一個基準元素，假設為第一個元素，將列表分成兩部分，將所有小於基準值的元素放在基準值前面，所有大於基準值的元素放在基準值後面，再分別對這兩部分重覆上面的步驟即可。代碼首先如下：

// key為基準值序號
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } else {
        var low = [];
        var high = [];
        var pivotkey = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (arr[i] <= pivotkey) {
                low.push(arr[i]);
            } else {
                high.push(arr[i]);
            }
        }
    }
    return quickSort(low).concat(pivotkey, quickSort(high));
}

快速排序的時間複雜度為O(nlogn),而且是一個不穩定的排序演算法。

歸併排序

歸併的含義是將兩個或兩個以上的有序表組合成一個新的有序表。假設初始序列長度為n，首先，每個子序列的長度為1，然後前後兩兩歸併。得到若幹個長度為2或者1的子序列，再兩兩歸併，如此重覆，直至得到一個長度為n的的有序序列為止。

原文鏈接http://hyuhan.com/2017/03/02/sorting-with-javascript/#歸併排序