JS排序之簡單排序

JS排序之簡單排序
- 冒泡排序
- 直接插入排序
- 直接選擇排序

冒泡排序

時間復雜度: O(n^2)
穩定的排序演算法
特點: 從后向前找,有序區數字一定全部小于(或大于)無序區數字
性能: 慢
優化: 雙向冒泡(雞尾酒排序)

    function bubbleSort(ary) {
        let exchange = 0, 
            temp = null,
             n = ary.length;
        // i<n-1 而不是 i<n, 當遍歷到n-1次時已近排好序了 >, 
        for(let i=0; i<n-1; i++) {
            // 從后面向前遍歷, 用前一項比后一項
            for(let j = n-2; j>=i; j--) {
                if(ary[j+1] < ary[j]) {
                    temp = ary[j];
                    ary[j] = ary[j+1];
                    ary[j+1] = temp;
                    exchange = 1;
                }
            }
            // 如果沒有發生交換(表明排序完成),直接退出排序
            if(exchange) break;
        }
        return ary;
    }

效果示例:

冒泡排序

直接插入排序

時間復雜度: O(n^2)
穩定的排序演算法
特點: 將單前元素插入前面有序區中排序, 有序區中元素不一定小于(大于)無序區元素
性能: 在陣列元素基本有序的情況下速度很快
優化: 設定增量, 讓陣列基本有序,然后在不斷縮減增強(希爾排序)

    function straightInsertionSort(ary) {
        let n = ary.length,
            temp = null;
        for (let i = 1; i < n; i++) {
            // 如果后一項小于前一項,說明需要交換
            if (ary[i] < ary[i - 1]) {
                // temp = 需要交換的項
                temp = ary[i];
                let j = i - 1;
                do {
                    // 前面的向后面移動
                    ary[j + 1] = ary[j];
                    j--;
                } while (j >= 0 && temp < ary[j]); // 找到temp需要插入的位置
                // 插入temp
                ary[j + 1] = temp;
            }
        }
    return ary;
    }

效果顯示:

直接插入排序.gif

直接選擇排序

時間復雜度: O(n^2)
不穩定的排序演算法
特點: 從前向后找到最小(最大)的, 然后和第一個交換, 有序區一定小于(大于)無序區
性能: 比冒泡強
不穩定原因: 元素的交換可能直接跨過多個元素,相等元素可能發生位置變化
- 例如: 553 => 排序時第一個5和3直接交換, 第一個5就到第二個5后面去了, 位置發生變化

    function straightSelectSort(ary) {
        let n = ary.length,
            temp = null;
        for(let i=0; i<n-1; i++) {
            let k = i;
            for(let j = i+1; j<n; j++) {
                // 找到最小值的位置
                if(ary[j]<ary[k]) k=j;
            }
            if(k!== i) {
                temp = ary[i];
                ary[i] = ary[k];
                ary[k] = temp;
            }
        }
        return ary;
    }

效果示例:

直接選擇排序.gif

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/140902.html

標籤：JavaScript

上一篇：js正則運算式總結

下一篇：JavaScript 原型與繼承

JS--排序演算法之簡單排序

JS排序之簡單排序

冒泡排序

直接插入排序

直接選擇排序