手机版
你好,游客 登录 注册
背景:
阅读新闻

Java八大排序算法之插入排序详解

[日期:2019-08-04] 来源:Linux社区  作者:十八岁 [字体: ]

八大排序算法之插入排序(动图演示 思路分析 实例代码Java 复杂度分析)

一、动图演示

二、思路分析

例如从小到大排序:

1.  从第二位开始遍历,

2.  当前数(第一趟是第二位数)与前面的数依次比较,如果前面的数大于当前数,则将这个数放在当前数的位置上,当前数的下标-1,

3.  重复以上步骤,直到当前数不大于前面的某一个数为止,这时,将当前数,放到这个位置,

  1-3步就是保证当前数的前面的数都是有序的,内层循环的目的就是将当前数插入到前面的有序序列里

4.  重复以上3步,直到遍历到最后一位数,并将最后一位数插入到合适的位置,插入排序结束。

根据思路分析,每一趟的执行流程如下图所示:

三、复杂度分析

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,所以平均时间复杂度为O(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));
    }
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-08/159800.htm

 

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款