超详细推导八大排序之插入排序

Dear 丶 2023-02-17 02:58 50阅读 0赞

插入排序思路：首先把一组数据分成两个部分，一部分是已经排好顺序的，这里我按照从小到大排列（这部分记作A），一部分是待排列数据（这部分记作B），默认排列好的部分只有一个数据也就是arr\[0\],然后将后面的数据依次与arr\[0\]比较，如果小于arr\[0\]则需要插入到arr\[0\]的前面（因为是从小到大的嘛）

没理解没关系，现在我举例详细说明：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
如图，此时默认排列好的数据只有arr\[0\],除此之外都是待排数据.首先进行第一轮排序比较。**这里的比较是从后向前比较，也就是从待排序元素后面的一个元素依次向前比较**。arr[1][]等于34小于arr\[0\],所以将34移到arr\[0\]后面。那么怎样移动呢？解决了这个，插入排序问题就迎刃而解了。

**规则如下：  
当前待插入的数据从它后面的一个元素依次向前比较，直到遇到了A部分有数据小于当前待插入的数据或者已经遍历到了开头arr\[0\]，(因为再向前比较数据下标就越界了嘛)。此时就找到了插入的位置，接下来就是将遍历过的（A部分）元素全部向前移动一位（arr\[pos + 1\] = arr\[pos\]）,也就是后面的元素覆盖前一个元素。所以经过移动过后，A部分肯定会空出一个位置，这个位置就是要插入的位置**。还是举例说明，如下图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]  
此时A部分有了两个排好的数据，接下来比较下一个待插入数据arr[2][]。因为arr[2][] > arr2 - 1，按照从小到大的规则，所以不需要动。所以如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]  
接着，待插入的元素成了arr[3][2],然后遍历A部分的数据直到遇见小于arr[3][2]的元素，及为插入位置，或者遍历到了arr\[0\]，此时就表示没有数据小于arr[3][2]，所以将遍历过的元素全部后移一位（arr\[ops\] + 1 = arr\[ops\]）,经过后移之后arr\[0\]的位置就空出来，所以直接插入待插入的数据，（arr\[0\] = temp.这里的temp已经保存了arr[3][2]的数据）,所以排列过后如图:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 4]  
后面就不做推导了，相信你已经明白了整个过程，接下来给出完整的代码：

//插入排序方法
        private static void insertSort(int[] arr){
        
            //因为初始待插入数据是从arr[1]开始的，所以初始化i= 1;
            for (int i = 1;i<arr.length;i++){
        
                int temp = arr[i];//存储当前要插入数据的值
                int insertPos = i - 1;//当前待插入元素的前一个元素的下标
                //说明：
                //inserPos > = 0是防止## 标题数组下标越界
                //temp < arr[insertPos]及表示当前待插入元素的值小于前一个元素（已经排好的元素）
                //当temp > arr[insertPos]则表示从大到小排列
                while (insertPos >= 0 && temp < arr[insertPos]){
        
                    arr[insertPos + 1] = arr[insertPos];//元素后移一位
                    insertPos --;//因为while循环里，在没有找到插入条件或者没有遍历到arr[0],会将排好部分的元素依次向后移一位
                }
                //内存循环结束表示找到了插入位置
                //进行插入
                arr[insertPos + 1] = temp;
            }
        }

综上，就完成了插入排序的全部推导，通过分析不难发现，插入排序设计到了大量的移动操作，假设待插入数据的最后一个数据非常小，所以就必须将已经排好的数据全部向后移动一位，这样效率就很低，所以之后我会介绍插入排序的优化——Shell排序,Shell会在插入排序的基础上大大优化性能。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/202006111726417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[1]: http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200611184142938.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200611184417197.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[2]: https://mermaidjs.github.io/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200611184915789.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200611190001174.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center