插入排序详讲：直接插入排序+希尔排序（图解+思路+代码）

文章目录

排序
- 一、排序的概念
- - 1.排序：
  - 2.稳定性：
  - 3.内部排序：
  - 4.外部排序：
- 二、插入排序
- - 1.直接插入排序
  - 2.希尔排序

排序

一、排序的概念

1.排序：

一组数据按递增/递减排序

2.稳定性：

在这里插入图片描述

待排序的序列中，存在多个相同的关键字，拍完序后，相对次序保持不变，就是稳定的

3.内部排序：

数据元素全部放在内存中的排序

4.外部排序：

数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

二、插入排序

1.直接插入排序

和整理扑克牌类似，将乱序的牌，按值的大小，插入整理好的顺序当中

从头开始，比最后一个小的话依次向前挪，直到大于之前牌时，进行插入

在这里插入图片描述

1.如果只有一个值，则这个值有序，所以插入排序， i 从下标1开始，把后面的无序值插入到前面的有序当中

2.j = i-1,是i的前一个数，先用tmp将 i位置的值（要插入的值）先存起来，比较tmp和j位置的值

3.如果tmp的值比 j位置的值小，说明要向前插入到有序的值中，把 j位置的值后移，移动到 j+1的位置，覆盖掉 i 的值

4.j 下标向前移动一位，再次和 tmp 比较

5.如果tmp的值比 j 位置的值大，说明找到了要插入的位置就在当前j位置之后，把tmp存的值，放到 j+1的位置

6.如果tmp中存的值比有序的值都小，j位置的值依次向后移动一位，j不停减1，直到排到第一位的数移动到第二位，j的下标从0移动到-1，循环结束，最后将tmp中存的值，存放到 j+1的位置，也就是0下标

    public void insertSort(int[] array) {

        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//tmp存储i的值
            int j = i - 1;
            for (; j >= 0; j--) {
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    // array[j+1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

插入就是为了维护前面的有序

元素越接近有序，直接插入排序算法的时间效率越高
时间复杂度O( N ² )
空间复杂度O ( 1 )
稳定性：稳定

如果一个排序是稳定的，可以改变实现为不稳定的

如果是不稳定的排序，则没有办法改变

2.希尔排序

希尔排序shellSort 叫缩小增量排序，是对直接插入排序的优化，先分组，对每组插入排序，让整体逐渐有序

利用了插入排序元素越有序越快的特点

在这里插入图片描述

先确定一个整数，把待排序数分成多个组，每个组中的数距离相同，
对每一组进行排序，然后再次分组排序，减少分组数，组数多，每组数据就少
找到分组数=1时，基本有序了，只需要再排一次插入排序即可

一开始组数多，每组数据少，可以保证效率

随着组数的减少，每组数据变多，数据越来越有序，同样保证了效率

到达1分组之前，前面的排序都是预排序

    public static void shellSort2(int[] array) {

        int gap = array.length;
        while (gap > 1) { //gap>1时缩小增量
            gap /= 2;//直接在循环内进行最后一次排序
            shell(array, gap);
        }

    }
    /**
     *
     * 希尔排序
     * 时间复杂度O(N^1.3---N^1.5)
     * @param array
     */

    public static void shellSort1(int[] array) {

        int gap = array.length;
        while (gap > 1) { //gap>1时缩小增量
            shell(array, gap);
            gap /= 2;//gap==1时不进入循环，再循环为再次排序
        }
        shell(array, gap);
        //组数为1时，进行插入排序
    }

    public static void shell(int[] arr, int gap) {
        //本质上还是插入排序，但是i和j的位置相差为组间距
        for (int i = gap ; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >=0; j -= gap) {
                if (tmp<arr[j]){
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }