前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法:插入排序详解--为什么从第二项开始,而不是第一项

算法:插入排序详解--为什么从第二项开始,而不是第一项

原创
作者头像
cMusketeer
发布2018-05-20 19:38:04
1.2K6
发布2018-05-20 19:38:04
举报
文章被收录于专栏:Android机器圈

PS:对于插入排序这个算法,我们想要看清他就要从它的应用场景,概念,用法等去了解它,实现代码就那么几行,但有时还真是不好理解,比如说为什么从第二项开始,而不是从第一项开始呢,下面我们来举个例子看一下。

概念:有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)

1:插入排序

代码语言:javascript
复制
/**
         * 从第二项开始,第一项默认为有序
         * 1:把第二项数据暂存,和第一项比较,如果第一项>第二项则调换,
         * 2:把第三项数据暂存,和第二项比较,如果第二项>第三项则调换, 这时调换后的第二项还要和第一项比较,然后再判断调换,从当前下标开始向左遍历凡是大于temp的数据,下标都均向右移动一位(调换)。
         * 以此类推 ........
         *
         *
         * 很多人估计不理解为什么从第二项开始,而不是从第一项,
         * 这里我稍微做一下解释,插入排序就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,
         * 我们对于一个数组,不知道哪里是排序好的,可能是前三条,也可能不是有序的,我们这时就要假设一段已经排好序的数组,我们直接取前三项的话,
         * 不一定是排序好的, 我们取前一项的话,就一个数据肯定是排序好的,所以就从第二项开始,默认第一项已经排序好了。这就是由来。
         */
        int insertElems[] = { 23, 4, 5, 34, 56, 21 };
        int inner, outer;
        for (outer = 1; outer < insertElems.length; outer++) {
            int temp = insertElems[outer];// 把第二项暂存
            inner = outer;
            // (第一项>第二项)
            while (inner > 0 && insertElems[inner - 1] > temp) {
                insertElems[inner] = insertElems[inner - 1];
                inner--;
            }
            insertElems[inner] = temp;
            for (int k = 0; k < insertElems.length; k++) {//遍历可删除
                System.out.print(insertElems[k] + " , ");
            }
            System.out.println();
 
        }

代码语言:java
复制
4 , 23 , 5 , 34 , 56 , 21 ,
4 , 5 , 23 , 34 , 56 , 21 ,
4 , 5 , 23 , 34 , 56 , 21 ,
4 , 5 , 23 , 34 , 56 , 21 ,
4 , 5 , 21 , 23 , 34 , 56 ,

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1:插入排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档