每天一点算法-直接插入排序 (Day5)

介绍

前面介绍的冒泡排序和快速排序属于排序算法中的交换排序。今天介绍的直接插入排序则属于插入排序，算法核心是从待排序数据中对比后加入有序数据直到所有数据都在待排序数据。算法逻辑（升序为例）：
1.以第一个数为第一轮的有序数组；
2.将第二个数以第一个数对比，大的放在后面，小的放前面，组成第2轮的有序数组；
3.以此类推，第n个数与第n-1轮的有序数组中的数据对比，遍历第n轮的有序数组，知道找到大于第n个数据的数，插入到这个数的前面；直到待排序数组为空；

例子

假设有一个待排序数组[77, 6, 37, 96, 34, 6, 14], js实现如下(升序)：

function sort(arr){
    let result = [arr[0]];
    for(let i = 1; i < arr.length; i++ ){
        for(let j = 0; j < result.length; j++){
            // 当待排序数小于排序数组的某个值时，插到这个数前面
            if(arr[i] <= result[j]){
                result.splice(j, 0, arr[i]);
                break;
             // 对比到有序数组的最后一个数据时扔没有小于的则直接放到后面
            }else if(j === result.length - 1){
                result.push(arr[i]);
                break;
            }
        }
    }
    return result;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

遍历次数的计算与冒泡排序类似：n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，所以时间复杂度为O(n^2)。

感谢阅读！欢迎关注！持续更新中...