插入排序原理（java实现）

桃扇骨 2022-06-10 06:49 150阅读 0赞

插入排序也是排序算法的一种，他的排序定义是这样：把一个数插入到一个有序数列的合理位置，并使插入后数列仍然有序，不断重复这个过程，就能使整个数组成为有序数列。  
　　  
　　听起来很难理解，对吧，不如我们举个例子，假定一个整型数组\{7,5,6,4,3,1,2\}，对他进行从小到大的排序，按照定义说的，把一个数插入到一个有序数列的合理位置，什么是有序数列呢，哪里来的有序数列呢，本来就是让变得有序，原来就有序那还用排序吗？博主刚开始也是很不理解为什么这么定义，后来才慢慢明白其中的道理  
　　  
　　比如上面说的这个数组，我们应该怎么看，首先看下标0和下标1位置中的数，7和5，先让他俩从小到大排好，5比7小，那就让5放到7的前面，于是就变成了\{5,7,6,4,3,1,2\}，现在，前两个数就是定义中说的有序数列了，对于刚刚比较的7和5来说，7这个数，就是定义中说的有序数列，好，我们完成剩余的过程  
　　  
　　再来看下标2，首先让他和下标1进行比较，6比7小，那么将7放到6的位置，拿6去跟下标0，也就是5，比较，6比5大，所以6应该放在5后面，下标1的位置，数组变成\{5,6,7,4,3,1,2\}，看到这里读者可能不明白了，为什么开始的时候就将7放到6的位置，别急，接着往下看  
　　  
　　看下标3，让他跟前一个数，下标2，也就是7比较，4比7小，那7往后移，放到4的位置，再拿4和下标1的数据进行比较，4比6小，那么6往后移，再拿4和下标0的数据进行比较，4比5小，那么5往后移，这时候，前面没有数据了，那么4就放到了下标0的位置，数组变成\{4,5,6,7,3,1,2\}  
　　  
　　后面的操作也是一样，依次把下标4，下标5，下标6中的数据拿出来跟前面的数进行比较，如果前面的数大，就让他往后移一个位置，直到前面的数不大于要插入的数了，再将其插入，看到这儿，你明白刚刚说的将7放到6的位置是为什么了吗？因为这个数据结构是数组，你要插入，就必须将各个元素往后移，才能空出位置，但是，要注意的是，往后移的同时，会产生数据覆盖，就比如第一轮说的7放到6的位置，那6就没了，所以怎么办？再定义一个整型变量target去保存这个数，防止数据覆盖，读者可以参照上面的例子和下面的代码，自己走一走步骤，就明白了  
　　  
　　下面是Java代码实现：

//插入排序原理
    class Demo
    {
        public static void main(String[] args)
        {
            //定义整形数组
            int[] arr = {
       2,1,3,5,7,6,4};
            //调用插入排序函数
            InsertSort(arr);
            //输出排序后的数组
            for(int i=0;i<arr.length;i++)
            {
                System.out.print(arr[i]+" ");
            }
        }
        //定义插入排序函数
        public static void InsertSort(int[] arr)
        {
            for(int i=1;i<arr.length;i++)
            {
                //将要比较的值赋值给target，否则将被覆盖，无法找到
                int target = arr[i];
                //定义j来控制下标
                int j = i;
                //当满足j>0并且target<arr[j-1]的时候，循环
                while(j>0 && target<arr[j-1])
                {
                    //满足target<arr[j-1]就把数组向后移
                    arr[j] = arr[j-1];
                    j--;
                }
                //循环结束后，j就是要插入的位置，将target赋值给arr[j]
                arr[j] = target;
            }
        }
    }