首页 > 编程语言 > 详细

排序算法 - 插入排序

时间:2020-03-28 12:23:29      阅读:51      评论:0      收藏:0      [点我收藏+]

算法思想:类似扑克牌的排序,先固定第0个元素,从第 1 个元素开始向前两两比较大小,然后交换位置

由于插入排序swap会导致性能下降,所以用赋值操作来代替交换达到优化的目的

性能优化思路:先固定第0个元素,从第1个元素开始,先把第1个元素复制一份保存起来,看一下此元素是否应该放在当前的位置(需要大小比较),如果不应该,那就把前一个元素放在当前位置,然后判断此元素是否应该放在前一个位置,否则继续向前依次比较,直到此元素放入到了合适的位置

插入排序的优势:找到合适的位置即可提前终止内层循环,对于近乎有序的数组,算法复杂度接近O^n级别

//插入排序
template<typename T> //模板函数/泛型
void insertionSort(T arr[],int n){
    for(int i=1; i < n ; i++){
        //寻找元素arr[i]合适的插入位置
        T e = arr[i];
        int j;//j 保存元素e应该插入的位置
        for(j = i;j > 0 && arr[j-1] > e ;j --){
            arr[j] = arr[j-1]; //可提前终止
        }
        arr[j] = e;
    }
}

 

排序算法 - 插入排序

原文:https://www.cnblogs.com/Erick-L/p/12586371.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!