排序算法之插入排序

插入排序

部分内容摘自《算法基础——打开算法之门》 首先先上代码

public class 插入排序 {
    public static void main(String[] args) {
        int n = 10;
        int[] t = {5, 1, 2, 3, 4, 6, 4, 9, 7,10};
        for (int i = 1; i < n; i++) {
            int key = t[i];
            int j=i-1;
            while (j >= 0 && t[j] > key) { //如果j光大于0,则对于第一个元素会直接忽略
                t[j + 1] = t[j];
                j--;
            }
            t[j + 1] = key;
        }
    }
}

所谓插入排序，就是将一个元素与位于该元素之前的元素依次进行比较，然后插入到合适的位置上，在比较过程中，不需要考虑该元素右侧的元素。

针对外部循环的循环不定式为

在第一步循环的每次迭代开始时，子数组A[0…i-1]包含初始元素A[0…i-1]，但此时是已经排好序的。

插入排序动图演示

在这里插入图片描述

原理： 每次执行循环时，先使用key变量来存储当前元素的值，因为在后续的移动过程中，该元素的值会被前一个元素覆盖，当找到一个合适的位置时，再将key插入。不停循环下去，当t[j]>key，也就是当前元素的值比key要大，即key插入到了合适的位置；或者当j<0，也就是该元素是整个数组中最小的元素，此时直接将该元素放到数组的最前面，同样完成排序。

插入排序的运行时间：

分析插入排序的运行时间，我们发现它比选择排序更复杂，选择排序的内层循环取决于外层循环的索引而非元素的值，而插入排序内层循环的迭代次数取决于外层循环的索引i和数组元素值。

最好情况： 对于每个i值，当第一次验证t[j]>key时就已经是错误的，此时即为最好情况。当且仅当程序开始时，数组已经是有序的，在这种情况下，外层迭代n-1次，每次迭代花费常量时间，所以时间复杂度是O(N)。 最坏情况： 当内层循环每次都执行了最大次数，会发生最坏情况，现在判定条件t[j]>key每次都为真并且每次都执行到j<0时，每个元素都要扫描比较到数组的最左侧，即元素为逆序时，为最坏情况。外层循环每次迭代花费常量时间，迭代n-1次，内层循环每次迭代也花费常量时间，迭代i-1次。因此最坏情况下时间复杂度为O(n2)。

选择排序与插入排序的优缺点： 当数组基本有序时，插入排序更好些。选择排序的优点在于每次移动的次数是固定的，而插入排序最坏情况下移动的次数可能会达到n2次。所以，如果无法确定插入排序的输入是否接近于最好情况，最好运行选择排序。