排序算法之插入排序

╰+哭是因爲堅強的太久メ 2023-02-23 03:52 12阅读 0赞

# 插入排序 #

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序数组和一个无序数组，开始时有序数组中只包含一个元素，无序数组中包含有n-1个元素，排序过程中每次从无序数组中取出第一个元素，把它依次与有序数组的元素进行比较，将它插入到有序数组中的适当位置，使之成为新的有序数组，直到最后无序数组没有元素为止。

## 算法步骤 ##

*  将待排序数组第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 *  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

## 动图演示 ##

![在这里插入图片描述][20200705093104107.gif]

## 算法实现 ##

for (int end = 1; end < array.length; end++) { 
        int cur = end;
        while (cur > 0 && cmp(cur - 1, cur) > 0) { 
            swap(cur - 1, cur);
            cur--;
        }
    }

## 算法优化 ##

将上面算法中的`交换`转为`挪动`，算法步骤如下：

1.  先将待插入的元素备份
2.  头部有序数组中比待插入元素大的，都朝尾部方向挪动1个位置
3.  将待插入元素放到最终的合适位置

for (int end = 1; end < array.length; end++) { 
    
        int cur = end;
        E curValue = array[cur]; // 备份
    
        // 大于待插入元素的后移一位
        while (cur > 0 && cmp(array[cur - 1], curValue) > 0) { 
            array[cur] = array[cur-1];
            cur--;
        }
    
        array[cur] = curValue; // 插入
    }

## 再次优化 ##

插入排序的过程中需要查找插入的位置，如果使用从有序数组后面往前遍历，那么查找的时间复杂度为O(n)，既然是查找，可以使用二分查找算法对查找部分逻辑进行优化，使得查找的时间复杂度降为O(logn)。

### 二分查找 ###

假设在`[begin,end)`范围内查找某个元素`v`，`mid=(begin+end)/2`

*  如果`v<m`，去`[begin,mid)`范围内二分查找
 *  如果`v>m`，去`[mid+1,end)`范围内二分查找
 *  如果`v==m`，直接返回`mid`

public static int search(int[] array, int v) { 
        int begin = 0;
        int end = array.length;
        while (begin < end) { 
    
            int middle = (begin + end) >> 1;
    
            if (v < array[middle]) { 
                end = middle;
            } else if (v > array[middle]) { 
                begin = middle + 1;
            } else { 
                return middle;
            }
    
        }
        return -1;
    }

### 插入排序中的二分查找优化 ###

上面的二分查找中如果存在多个重复的值，返回哪个是不确定的，所以会造成插入排序的不稳定，下面会对二分查找进行优化。

要保证插入排序的稳定性，二分查找返回的插入位置必须为第一个大于`v`的元素位置，具体算法步骤如下：

假设在`[begin,end)`范围内查找某个元素`v`，`mid=(begin+end)/2`

*  如果`v<m`，去`[begin,mid)`范围内二分查找
 *  如果`v≥m`，去`[mid+1,end)`范围内二分查找

使用二分查找优化的插入排序代码如下：

for (int end = 1; end < array.length; end++) { 
    
         // 备份
         E v = array[end];
    
         // 二分查找待插入的位置
         int left = 0;
         int right = end;
         while (left < right) { 
    
             int middle = (left + right) >> 1;
    
             if (cmp(v, array[middle]) < 0) { 
                 right = middle;
             } else { 
                 left = middle + 1;
             }
         }
    
         // [left, end)元素右移一位
         for (int i = end; i > left; i--) { 
             array[i] = array[i - 1];
         }
    
         // 插入
         array[left] = v;
     }

需要注意的是，使用了二分查找后，只是减少了比较次数，移动次数并没有减少，所以插入排序的平均时间复杂度依然是O(n^2)。

## 逆序对（Inversion） ##

数组\{2,3,8,6,1\}的逆序对为：<2,1>、< 3,1> <8,1> <8,6> <6,1>，共5个逆序对。

插入排序的时间复杂度与逆序对的数量成正比关系，逆序对的数量越多，插入排序的时间复杂度越高。

当逆序对的数量极少时，插入排序的效率特别高，甚至速度比O(nlogn)级别的快速排序还要快。

数据量不是特别大的时候，插入排序的效率也是非常好的。

插入排序的最坏、平均时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)，是一个稳定的排序算法。

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[20200705093104107.gif]: https://img-blog.csdnimg.cn/20200705093104107.gif
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg