插入排序

作者: XiMiMax | 来源:发表于2017-08-06 13:45 被阅读82次

    上一篇我们我们简单的介绍了算法及学习的目的(个人理解),今天我们来学习下插入排序


    我们用一个简单的数组来帮助我们学习本篇内容

    int[] b = { 4, 2, 3, 6, 1, 5 };
    我们定义一个数组,要求输出结果为{1,2,3,4,5,6}

    那么怎么去理解这个问题呢?

    就像排队(按高矮)一开始只有一个人,每来一个就和队伍里的人进行对比一下,找到自己合适的位置

    实际排序过程

    上图中,黑色背景块为新加入的,灰色为已排序的
    每个新加入的与已排序的进行比较找到自己的位置,然后进入下一次循环

    
            int[] b = { 4, 2, 3, 6, 1, 5 };
            int i, j;
            int temp;
            for (i = 1; i < b.length; i++) {
                temp = b[i];//获取新加入的值
                j = i - 1;
                while (j > -1 && temp < b[j]) {//如果新加入的小于已排序的,位置替换
                    b[j + 1] = b[j];
                    j--;
                }
                b[j + 1] = temp;
    
               //输出每次的排序结果
                for (int i1 = 0; i1 < b.length; i1++) {
                    System.out.print(b[i1] + " ");
                }
                System.out.println("");
            }
    

    在上面的 for 循环中,下标 i 指正在被插入的数(temp)每次循环开始包含元素b[0..i]的子数组构成已排序的,剩余的b[i+1..b.length]则对应未排序的
    事实上 b[0..i] 就是原来 0 到 i 的数,只不过进行了排序

    输出结果

    1|    2 4 3 6 1 5 
    2|    2 3 4 6 1 5 
    3|    2 3 4 6 1 5 
    4|    1 2 3 4 6 5 
    5|    1 2 3 4 5 6 
    

    输出结果,可以看出循环了5次
    细心的会发现第二次和第三次输出结果是一样的,结合上图实例,第三次循环插入了6 ,而6>4,位置不变;
    当第四次循环插入1时,则需要和前面的每一位进行比较,然后确定自己的位置,这个就是时间复杂度

    时间复杂度是指执行算法所需要的计算工作量

    插入排序
    最好的情况下(已排序:{1,2,3,4,5,6})此时只需要对比前一位,此时的时间复杂度为O(N)
    最坏情况(逆序:{6,5,4,3,2,1})此时每插入都要对比前所有的数,此时的时间复杂度为O(N^2)
    (N:此处指数组长度)

    每星期至少一篇跟新本系列,感兴趣可以关注,如有疑问欢迎留言。
    一起学习,一起进步。

    相关文章

      网友评论

        本文标题:插入排序

        本文链接:https://www.haomeiwen.com/subject/wwbglxtx.html