小白懂算法之插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了小白懂算法之插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2623字，纯文字阅读大概需要4分钟。

内容图文

前言

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

一.插入排序原理

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

二.图解

三.实现思路

　　插入排序分为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]+" ");
        }
    }

　　测试结果：

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

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

内容总结

以上是互联网集市为您收集整理的小白懂算法之插入排序全部内容，希望文章能够帮你解决小白懂算法之插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---