【算法】排序算法—插入排序

文章目录

插入排序

思路分析：
一个数组可以当成两个表，一个有序表，一个无序表。一开始认为数组的第一个元素是有序的，依次将其后面的元素插入到这个有序表中来，直到整个表有序为止。也就是将无序表中的元素插入到有序表中。
图解算法：

代码实现

import java.util.Arrays;/**
 * @Author 不知名网友鑫
 * @Date 2022/3/21
 **///从小到大排序publicclassInsertSort{publicstaticvoidmain(String[] args){int[]a={4,3,2,1,6,-1};//第一层for循环控制插入轮数，由于把第一个数当成有序列表，所以只需要a.length-1轮。for(int i=1;i<a.length;i++){//表示待插入数的值。int insertVal=a[i];//表示待插入的数的前一个索引int insertIndex=i-1;//insertIndex >= 0 判断insertIndex是否越界//a[insertIndex]>insertVal 说明当前点不是插入点。boolean flag=true;while(insertIndex >=0&&  a[insertIndex]>insertVal){
                flag=false;//不是插入点，即将数后移。
                a[insertIndex+1]=a[insertIndex];//向前寻找插入点。
                insertIndex--;}//退出while循环，则表示已经找到当前的插入点，就是insertIndex+1的位置。//优化//如果执行了while语句，则表示插入点已经移动。//如果未执行while语句，表示当前点符合条件，则不需要进行插入。if(!flag){
                a[insertIndex+1]=insertVal;}}
        System.out.println(Arrays.toString(a));}}

算法的时间复杂度O(n^2)

该算法的时间复杂度为

O(n^2)

，接下来测试一把当

n=100000

时，程序的运行效率如何。

import java.text.SimpleDateFormat;import java.util.Date;/**
 * @Author 不知名网友鑫
 * @Date 2022/3/21
 **///从小到大排序publicclassInsertSort{publicstaticvoidmain(String[] args){int[]a=newint[100000];for(int i=0;i<a.length;i++){
            a[i]=(int)(Math.random()*100000);}
        Date date=newDate();
        SimpleDateFormat simpleDateFormat=newSimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String s=simpleDateFormat.format(date);
        System.out.println("插入排序前的时间是"+ s);InsertSort(a);

        Date date1=newDate();
        String s1=simpleDateFormat.format(date1);
        System.out.println("插入排序之后的时间是"+s1);}publicstaticvoidInsertSort(int[]a){//第一层for循环控制插入轮数，由于把第一个数当成有序列表，所以只需要a.length-1轮。for(int i=1;i<a.length;i++){//表示待插入数的值。int insertVal=a[i];//表示待插入的数的前一个索引int insertIndex=i-1;boolean flag=true;//insertIndex >= 0 判断insertIndex是否越界//a[insertIndex]>insertVal 说明当前点不是插入点。while(insertIndex >=0&&  a[insertIndex]>insertVal){//不是插入点，即将数后移。
                flag=false;
                a[insertIndex+1]=a[insertIndex];//向前寻找插入点。
                insertIndex--;}//退出while循环，则表示已经找到当前的插入点，就是insertIndex+1的位置。//优化//如果执行了while语句，则表示插入点已经移动。//如果未执行while语句，表示当前点符合条件，则不需要进行插入。if(!flag){
                a[insertIndex +1]= insertVal;}}}}

小结：
由此可见，插入排序在处理大量数据时存在一定的优势，其运行的时间比冒泡排序和选择排序的时间都要短。

如果觉得写的还不错的话，欢迎点一个⭐收藏⭐再走哦~~~