插入排序

什么是插入排序

插入排序，可以类比于我们平时玩扑克牌，当我们对扑克牌进行顺序的调整的时候，使用的思想，就是插入排序；
分析

对于一个随机乱序的数组，我们先设置一个索引，指向数组的第二个元素，然后让第二个元素与其左边的元素进行比较，如果第二个元素小于第一个元素，则交换二者位置，这样我们就可以保证第一、二两个元素的次序是正确的，这里注意，仅仅是保证次序是对的，保证不了位置是对的；
接着，将索引指向下一个元素，也就是第三个元素；然后，让第三个元素与其左边的元素进行比较；先与第二个元素比较，这里分为两种情况：
- 如果大于第二个元素，则无需再与第二个元素的左边的元素，进行比较，因为，第二个元素即其左边元素的次序已经排完了，第三个元素已经大于左边最大的元素了，所有，不用再进行比较了；将所有指向下一个元素，第四个元素；
- 如果小于第二个元素，则交换它们的位置；交换完位置，再与第一个元素进行比较：
  - 如果大于第一个元素，同样的道理，不需要再与左边剩下的元素进行比较了，移动索引到下一个元素；
  - 如果小于第一个元素，则交换位置，此时，到达数组的最左侧，结束比较，将索引移动到下一个元素；
…..
…..

当索引移动到第N个元素的时候，可以保证左边的 N-1 个元素的次序是正确的；

java代码实现

代码中的Example类的具体实现，请看博客中的Example类

 Integer[] a = {12, 2, 5, 6, 77, 6, 7, 4, 87, 23};
        int N = a.length;

//        开始时，索引置于数组的第二个元素
        for (int i = 1; i < N; i++) {
//            与索引左边的元素，进行比较
//            比较的结束条件:
//                              1、索引元素不小于索引左边的元素
//                              2、插入的元素，已经到达数组最左边，这样无法再进行新的比较了
            for (int j = i; j > 0 && Example.less(a[j], a[j - 1]); j--) {
                Example.exch(a, j, j - 1);
            }
        }
        Example.show(a);
    }

复杂度

插入排序存在不确定性，它的交换和比较，取决于输入，我们也不知道 Example.less(a[j], a[j - 1]) 这句代码是否为真；

最好情况下：数组本来就有序，则需要0次交换；因为，比较是从数组的第二个元素开始，所以，只需要N-1次比较；
最坏情况下：数组是完全逆序的，则每此比较都需要交换一次；从代码中看出，如果每次Example.less(a[j], a[j - 1]) 都为真，则一共进行了（n-1）+（n-2）+….+2+1 次，跟选择排序一样，是 n^2 次；
平均情况：
- 交换次数：( 0 + $n^{2}$ ) / 2
- 比较次数：( n - 1 + $n^{2}$ ) / 2

因此，相比较于选择排序的复杂度固定为 $n^{2}$ ,插入排序要比他快一点，大概是选择排序的 2 倍；

特点

实际交换次数与数组中，倒置元素的数量相等

有一对倒置元素，则需要交换一次；
例如数组：1、3、2、5、4 ；其中3与2 的次序是倒置的；5与4的次序是倒置的；一共有2对倒置元素，所以需要交换两次；

适用场景

虽然说插入排序的复杂度，最坏的情况下，复杂度是n^2 ；但是对于一些场景，插入排序非常有效；

数组中每个元素的位置，距离它最终的位置不远；
一个有序的大数组接一个小数组；
数组中倒置元素不多；

多说一句，如果数组的中倒置元素很少的时候，插入排序可能是最快的算法；

插入排序

目录

插入排序

java代码实现

复杂度

特点

适用场景