JS排序演算法之快排和歸併

目錄

• JS排序演算法之快排和歸併
  • 快速排序
  • 歸併排序

快速排序

原理: 選擇一個key(一般是第一個元素), 將數組劃分為兩個區域. 左邊全部區域小於等於key, 右邊全部大於key. 然後在通過這種方法將每個區域劃分為兩個區域. 整個過程可以遞歸實現,以此實現整個數據有序

• 時間複雜度: O(n*log(n))
• 最壞時間複雜度: O(n^2)
  • 最壞情況: 原數組是升序(降序), 需要排成降序(升序)
• 不穩定的排序
• 特性: 數組分塊,且左邊區域小於右邊(升序)
• 不穩定原因: 元素交換是跨元素直接交換, 相鄰相同元素可能發生位置交換
• 性能: 最好的的快速排序方法

示例過程:

function quickSort(ary) {
    let n = ary.length;
        function sort(ary, start, end) {
            if(end <= start) return;
            let i = start,
                j = end,
                key = ary[start]; // 設置第一個元素為key
            while(true) {
                // 從左向右找到大於key的元素位置(大於key迴圈停止, i就是該元素位置)
                while(ary[++i] < key) {
                    // 到達末尾退出迴圈
                    if(i === end) break;
                }
                // 從右向左找到小於key的元素位置
                while(ary[--j] > key) {
                    // 到達頭部退出迴圈
                    if(j === start) break;
                }
                // 如果 i和j相交, 直接退出迴圈
                if(i>=j) break;
                // 交換左右兩邊元素
                let temp = ary[i];
                ary[i] = ary[j];
                ary[j] = temp;
            }
            // 交換key和最後一個小於key值的元素(就是arr[j])
            let temp = ary[start];
            ary[start] = ary[j];
            ary[j] = temp;
            sort(ary, start, j);
            sort(ary, j+1, end);
        }
    sort(ary, 0, n);
    return ary;
}

效果演示:

歸併排序

原理: 先將數組不斷折分為左右兩個小數組, 然後再對小數組排序併合並起來

• 時間複雜度: O(n*log(n))
• 穩定的排序演算法
  • 穩定原因: 排序是兩兩元素值之間的互換, 相鄰相同元素位置不會被改變
• 性能: 速度僅次與快排(如果使用遞歸方法,在處理龐大數據時可能出現記憶體不足情況), 比快排穩定,任何時候時間複雜度都是O(n*long(n));
• 特點: 數組會不斷對半平分, 然後再排序合併. 先小區間有序,再大區間, 區間間隔相等.
• 優化: TimeSort排序

示例過程:

    function mergeSort(items) {
        if (items.length == 1) {
            return items;
        }
        //將數組對半平分為左右兩個數組
        var middle = Math.floor(items.length / 2),
            left = items.slice(0, middle),
            right = items.slice(middle);

        function merge(left, right) {
            var result = [];
            // 通過這個迴圈來排序
            while (left.length > 0 && right.length > 0) {
                if (left[0] < right[0]) {
                    /*shift()方法用於把數組的第一個元素從其中刪除，並返回第一個元素的值。*/
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }
            //合併兩個數組
            return result.concat(left).concat(right);
        }

    // 遞歸調用
    return merge(mergeSort(left), mergeSort(right));
}

效果示例

gif來源: 排序演算法-散點可視化