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]));

参考资料