Java的直接插入排序

╰+攻爆jí腚メ 2022-05-13 09:30 120阅读 0赞

## 直接插入排序 ##

直接插入排序是一种简单插入排序，基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程   
![这里写图片描述][SouthEast]   
  类似我们摸牌，一开始有一堆牌（待排序的）。由于第一次摸牌时手中没牌，所以不需要排序。第二次摸牌时和手中第一张拍比较，如果它大，就放在它的后面。 每次摸牌都会把牌放在一个前面比自己小（或等于），后面比自己大（或等于）的位置。   
![这里写图片描述][SouthEast 1]   
  **直接插入排序的Java代码**

public class Insertion {
    
        /**
         * 直接插入排序算法方法
        */
        public static void sort(int intArrays[]){
            int length=intArrays.length;
            int i,j;
            for(i=1;i<length;i++){
                for(j=i-1;j>=0&&intArrays[i]<intArrays[j];j--){
                    //intArrays[i]代表要插入的数字，intArrays[j]代表需要比较大小的数字，j递减
                    //当intArrays[i]大于intArrays[j]时（intArrays[i]插入的位置，也就是说插在j的后一位）或者intArrays[i]为当前数组的最小值时（此时的j为-1,也就是说intArrays[i]要插在第一位）返回j
                }
                //将intArrays[i]保存住，因为要j以后的数组向后移一位
                int temp=intArrays[i];
                for(int k=i;k>j+1;k--){
                    //将i到j范围的数组向后移一位
                    intArrays[k]=intArrays[k-1];
                }
                //intArrays[i]插在j的后一位
                intArrays[j+1]=temp;
            }
        }
    
        /**
         * 执行入口，intArrays：待排序的数组，displaySort：是否显示排序前和排序后的内容
         */
        public static void run(int intArrays[],boolean displaySort){
            int arrays[]= intArrays.clone();
            if(displaySort){
                NumberUtils.display(arrays,1);
            }
            long startTime=System.currentTimeMillis();
            sort(arrays);
            long endTime=System.currentTimeMillis();
            if(displaySort){
                NumberUtils.display(arrays,2);
            }
            System.out.println("插入排序用时："+(endTime-startTime)+"毫秒");
        }
        /**
         * 测试排序用的主方法
        */
        public static void main(String[] args){
            //数组长度
            int length=30000;
            //最大值
            int max =100000000;
            //是否打印排序后的内容
            boolean display=true;
            //随机获取的排序数组
            int intArrays[]= NumberUtils.getRandomArs(length,max);
            //插入排序
            Insertion.run(intArrays,display);
        }
    }

**运行main方法，终端输出**

排序前：52096862 89211005 17092175 60370534 40302430 53897879 34127111 43318378 29195095 ......44543512 40238517 99995921 49109471 44841738 2383202 81685348 82456235 16748589 90004692 
    排序后：1432 1466 8523 10963 16793 17166 17239 20386 23581 ......99961843 99967372 99967545 99967909 99979

[SouthEast]: /images/20220513/4723930d03134ba6a9777c92281193ca.png
[SouthEast 1]: /images/20220513/ab1ddbda9d7141a38daf83022459559b.png