Insertion sort 插入排序法

Insertion sort 插入排序法
Categories:
Tags:

複雜度

複雜度 Big O
最差時間複雜度 Worst-case time complexity Big O(n^2)
平均時間複雜度 Average-case time complexity Big theta (n^2)
最佳時間複雜度 Best-case time complexity Big omega (n)
空間複雜度 Space complexity Big O (1)

演算法

1. 確保檢查元素的左方是排序好的陣列

將陣列切割為左右兩方，左方確保一定是排序好的陣列

所以右方的陣列會取第一個數字，與左方陣列最大（最右方）數字做比較

若數字較小，則會繼續往左方移動比較，直到數字左方沒有任何數字小於本身數字就停止

2. 繼續取右方剩餘數字與左方排序好的數字陣列做比較

3. 持續這個步驟，將剩餘的陣列元素做比較

持續地將最小元素比較放左方正確順序的位置，最後就可以得到已排序的陣列

Insertion sort 插入排序法

程式

JavaScript

function insertionSort(sortNumberList) {
    for (var checkNumberIndex = 1; checkNumberIndex < sortNumberList.length; checkNumberIndex++) {
        // 從第 2 個數字開始檢查比較
        for (var insertNumberIndex = checkNumberIndex - 1; insertNumberIndex > -1; insertNumberIndex--) {
            // 從要插入的數字持續向左半部分比較，較小的數字持續交換移動到左方
            // 取得要插入數字位置的左右比較數字
            var leftNumber = sortNumberList[insertNumberIndex];
            var rightNumber = sortNumberList[insertNumberIndex + 1];
            if (leftNumber > rightNumber) {
                // 當「左方數字」比「右方數字」大，將兩個數字交換，大的數字放在右方
                [sortNumberList[insertNumberIndex+1],sortNumberList[insertNumberIndex]] = [sortNumberList[insertNumberIndex],sortNumberList[insertNumberIndex + 1]];
            }
        }
    }
    ;
    return sortNumberList;
}
console.log(insertionSort([23, 1, 10, 5, 2]));

TypeScript

function insertionSort(sortNumberList: number[]){

    for(let checkNumberIndex = 1; checkNumberIndex < sortNumberList.length;checkNumberIndex++){
        // 從第 2 個數字開始檢查比較

        for(let insertNumberIndex = checkNumberIndex - 1; insertNumberIndex > -1; insertNumberIndex--){
            // 從要插入的數字持續向左半部分比較，較小的數字持續交換移動到左方
            // 取得要插入數字位置的左右比較數字
            let leftNumber = sortNumberList[insertNumberIndex];
            let rightNumber = sortNumberList[insertNumberIndex + 1];

            if(leftNumber > rightNumber){
                // 當「左方數字」比「右方數字」大，將兩個數字交換，大的數字放在右方
                [sortNumberList[insertNumberIndex+1],sortNumberList[insertNumberIndex]] = [sortNumberList[insertNumberIndex],sortNumberList[insertNumberIndex + 1]];
            }
        }
    };

    return sortNumberList;
}

console.log(insertionSort([23, 1, 10, 5, 2]));

參考資料