小白懂算法之插入排序

前言

真的，看到挺多博客的插入排序，思路大多都是对的，但是在代码实现上不严谨，甚至还有的跟冒泡排序搞混了，还是有必要分析波插入排序，希望能帮助到大家。

一.插入排序原理

插入排序原理是： 逐步构建有序的序列 ，在 已排序序列中 从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

二.图解

三.实现思路

插入排序分为3种情况：

1.当前节点<前面的A节点时，A节点后移一位，接着向前继续比较。

2.当前节点>前面的A节点时，当前节点插入到A节点的后一个位置，此时不需要再继续比较了，因为A节点及之前的元素已经是有序的了

3.当前节点<前面的A节点时，并且A节点的位置是0时，需要连续两步操作：A节点往后移一位，当前节点插入到数组下标为0的位置。

如果这个思路看不懂没关系，请看代码，有更详细的解释。

四.代码实现

语言采用Java来实现，如果看不懂java代码关系也不大，基本每行都有解释

    /**
     *     实现思路：
     *         插入排序需要考虑3种情况：
     *             1.当前节点<前面的A节点时，A节点后移一位，接着继续比较
     *             2.当前节点>前面的A节点时，当前节点插入到A节点的后一个位置，此时不需要再继续比较了，因为A节点及之前的元素已经是有序的了
     *             3.当前节点<前面的A节点时，并且A节点的位置是0时，需要连续两步操作：A节点往后移一位，当前节点插入到数组下标为0的位置
     * 
     */
    public static int[] InsertionSortByFor(int[] arr) {
        
        /**
         *     最多遍历arr.length-1轮，i的值表示每轮从哪个位置开始向前比较；
         *     比如arr[1]，那么arr[1]就和arr[0]进行比较
         *     arr[2]，从arr[2]向前扫描比较
         *     arr[3],从arr[3]向前扫描比较
         *     依次类推
         */
        for(int i=1;i<arr.length;i++) {    
            int temp = arr[i];        //temp是保存着每轮当前节点的值，保存的目的是用于与前面的值做比较
            for(int j=i-1;j>=0;j--) {    //j的值记录的是当前节点的前面元素的下标位置;
                                        //只要满足j>=0，元素的比较才能进行，若j<0就会超出数组下标的范围
                                        //j--才能比较前面的元素
                if(temp<=arr[j]) {    //当前节点<前面的A元素，那么A元素往后移
                    arr[j+1] = arr[j];
                    if(j==0) {    //这里属于特殊情况，当temp<=arr[j]以及j==0时，需要连续两步操作：1.A元素往后移 2.当前节点插入到arr[0]的位置
                        arr[j] = temp;
                    }
                }else{    //当前节点>前面的A元素,那当前节点插入到A元素的后面，即j+1的位置
                    arr[j+1] = temp;
                    break;    //break是到这一步就不需要再往前比较了，因为A元素及之前的元素已经是有序了
                }
            }
            
        }
        return arr;
    }

main方法测试：

    public static void main(String[] args) {
        //创建一个无序数组
        int[] arr = new int[] {3,6,1,87,90,34,34,25};
        //调用插入排序方法，返回一个排序后的数组
        int[] sortedArr = InsertionSortByFor(arr);
        //遍历数组
        for(int i=0;i<sortedArr.length;i++) {
            System.out.print(sortedArr[i]+" ");
        }
    }

测试结果：

其实说得挺详细的了，基本都有注释，如果有不懂欢迎大家下面留言，上面的代码其实还有优化的空间，只不过临时写的，一些细节可能处理不到位请见谅

可以的话给个推荐，让我知道你来过！