请选择 进入手机版 | 继续访问电脑版
查看: 1414|回复: 0

【Java编程】Java八大排序算法之插入排序详解

[复制链接]

  离线 

 成长值: 2260

  • TA的每日心情
    开心
    4 天前
  • 签到天数: 76 天

    [LV.6]常住居民II

    346

    主题

    402

    帖子

    2452

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    2452
    发表于 2019-10-13 12:34:11 | 显示全部楼层 |阅读模式
    来源:Linux社区  作者:十八岁
    八大排序算法之插入排序(动图演示 思路分析 实例代码Java 复杂度分析)

    一、动图演示:

    【Java编程】Java八大排序算法之插入排序详解

    【Java编程】Java八大排序算法之插入排序详解
    二、思路分析:

    1.  从第二位开始遍历,
    3.  重复以上步骤,直到当前数不大于前面的某一个数为止,这时,将当前数,放到这个位置,
    4.  重复以上3步,直到遍历到最后一位数,并将最后一位数插入到合适的位置,插入排序结束。
    根据思路分析,每一趟的执行流程如下图所示:

    【Java编程】Java八大排序算法之插入排序详解

    【Java编程】Java八大排序算法之插入排序详解


    三、复杂度分析:
    1.  时间复杂度:插入算法,就是保证前面的序列是有序的,只需要把当前数插入前面的某一个位置即可。
    所以如果数组本来就是有序的,则数组的最好情况下时间复杂度为O(n)
    如果数组恰好是倒=倒序,比如原始数组是5 4 3 2 1,想要排成从小到大,则每一趟前面的数都要往后移,一共要执行n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n2 - 0.5 * n次,去掉低次幂及系数,所以最坏情况下时间复杂度为O(n2)
    平均时间复杂度(n+n2]
    2.  空间复杂度:插入排序算法,只需要两个变量暂存当前数,以及下标,与n的大小无关,所以空间复杂度为:O(1)

    四、Java 代码如下:
    import java.util.Arrays;
    public class insertSort {
        public static void main(String[] args) {
            int[] n = new int[]{20,12,15,1,5,49,58,24,578,211,20,214,78,35,125,789,11};
            int temp = 0,j;
            for (int i = 1; i < n.length; i++) {
                temp = n[i];
                for (j = i; j >0; j--) {
                    //如果当前数前面的数大于当前数,则把前面的数向后移一个位置
                    if(n[j-1]>temp){
                        n[j] = n[j-1];
                      
                        //第一个数已经移到第二个数,将当前数放到第一个位置,这一趟结束
                        if(j==1){
                            n[j-1] = temp;
                            break;
                        }

                    }else{//如果不大于,将当前数放到j的位置,这一趟结束
                   
                        n[j] = temp;
                        break;
                    }
                }
                System.out.println(Arrays.toString(n));
            }
            System.out.println(Arrays.toString(n));
        }
    }

    我知道答案 本帖寻求最佳答案回答被采纳后将获得系统奖励20 金钱 , 目前已有0人回答
    温馨提示:
    1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
    2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
    3、根据二○○二年一月一日《计算机软件保护条例》规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!谢谢
    4、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
    5、注册会员通过任何手段和方法针对论坛进行破坏,我们有权对其行为作出处理。并保留进一步追究其责任的权利。
    6、本站所有资源来自互联网,版权归原作者所有,所有资源仅供于学习、交流研究,请于下载24小时之后删除!
    7、当您在浏览本站时,发现有您自己创作的原创资源时侵犯了您的合法资源时,请您及时联系管理员,邮箱:2550721739@qq.com,我们会及时处理!
    使用 高级模式(可批量传图、插入视频等)
    您需要登录后才可以回帖 登录 | 立即注册