排序算法-插入排序

1. 直接插入排序Insert Sort

1.1 Insert Sort介绍

Insert Sort也是一种简单的内部排序算法，其是对待排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的，是一种稳定的排序算法。

Inser Sort的基本思想是：将待排序序列看作一个有序表和一个无序表，初始时有序表仅包含一个元素，而无序表中包含n - 1个元素。排序的过程中每次都取无序表中的第一个元素，将其依次与有序表中的元素进行比较，把它插入到有序表中的适当的位置，建立一个新的有序表，每轮排序都使得有序表长度 + 1，无序表长度 - 1。

1.2 图解说明Insert Sort步骤

举一个例子来具体说明直接插入排序法的过程。给出一个无序数列：55，85，21，12，5使用直接插入排序将其排列成一个从小到大的有序数列。

1. 定义两个临时变量insertValue和insertIndex分别表示待插入元素和该待插入元素想要要插入的位置；
2. 第一轮Insert Sort排序，nums[0] == 55 为有序区，选择无序区的第一个元素inserValue = nums[1] == 85，inserIndex = 0，与有序区中的元素比较，nums[1] > nums[0]，不需要往前插入，也即找到了nums[1]应插入的位置（就是原本nums[1]的位置），将nums[1]并入有序区；
3. 第二轮，选择无序区的第一个元素insetValue = nums[2] == 21，insertIndex = 1，逐一与有序区的元素比较，发现nums[2] < nums[1]，首先将num[1]的值后移，并令insertIndex--（insertIndex == 0），再次进行比较，nums[2] < nums[0]，将nums[0]的值后移同时insertIndex--（insertIndex == -1），此时找到了nums[2]应插入的位置（即应插入到nums[0]的位置）进行插入；
4. 重复执行上述过程，每一轮都使得有序区长度 + 1，无序区长度 - 1，直至无序区元素全部插入完毕。

1.3 Insert Sort时间复杂度分析

• 最好情况时间复杂度：O(n)

  最好情况下即数组本身就是按序排列，那么每趟排序都只进行一次比较，不需要移动元素。

• 最坏情况时间复杂度：O(\(n^2\))

  最坏情况下每趟排序都要与前面的元素进行比较且每次比较都要移动元素。

• 平均时间复杂度：O(\(n^2\))

1.4 代码实现

package com.algorithm;

import java.util.Arrays;

/**
 * @author SnkrGao
 * @create 2023-04-14 19:27
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] nums = {6,1,9,2,3,7,19,15};
        System.out.println("排序前的数组为：");
        System.out.println(Arrays.toString(nums));
        System.out.println("---------------------------------");

        insertSort(nums);

        System.out.println("---------------------------------");
        System.out.println("排序后的数组为：");
        System.out.println(Arrays.toString(nums));

    }

    public static void insertSort(int[] nums) {

        // 初始时有序区长度为1，因此无序区应从nums[1]开始
        for (int i = 1; i < nums.length; i++) {
            int insertValue = nums[i]; // 表示待插入元素
            int insertIndex = i - 1; // 表示该待插入元素初始时想要插入的位置，因为insertValue要与前一个元素比较

            while (insertIndex >= 0 && insertValue < nums[insertIndex]) {
                // 满足比较的条件，就要将nums[insertIndex]后移，并继续向前比较
                nums[insertIndex + 1] = nums[insertIndex];
                insertIndex--;
            }

            // 循环退出，找到insertValue应插入的位置为insertIndex + 1，因为在循环中执行了insertIndex--
            nums[insertIndex + 1] = insertValue;

            System.out.println("第" + i + "轮排序结果为：");
            System.out.println(Arrays.toString(nums));
        }
    }
}

2. 希尔排序Shell Sort

2.1 Shell Sort介绍

Shell Sort是希尔于1959年提出的一种排序算法，Shell Sort也是一种插入排序算法，其是对直接插入排序的一种改进，引入了增量（gap）的概念，也称为缩小增量排序。Shell Sort是一种不稳定的排序算法。

Shell Sort的基本思想是：Shell Sort可以与Insert Sort类比来理解，Shell Sort采用了跳跃式分组的概念，通过某个增量gap将待排序序列分为若干组，然后分组进行Insert Sort，每一轮所有分组的Insert Sort执行完毕后，逐步缩小gap，继续按组进行Insert Sort操作，直至gap为1时，整个序列被分为一组，此时序列已达到宏观上的基本有序，再执行一轮Insert Sort完成排序算法终止。

说明：

1. Shell Sort是Insert Sort的改进版，Shell Sort会执行多轮Insert Sort；
2. Shell Sort每轮执行Insert Sort时与单纯的Insert Sort有区别，其不是一个挨一个地比较插入，而是隔几个元素（gap）比较插入一次，这个gap不是固定的，而是逐渐缩小的，即每轮执行的Insert Sort增量都不一样；
3. Shell Sort有两种实现方法：交换式和移位式，但交换式会出现多次元素交换，造成很大程度的时间浪费，本文主要介绍效率较高的移位式，实际上交换式和移位式的基本思想是一致的。

2.2 图解说明Shell Sort步骤

举一个例子来具体说明希尔排序法的过程。给出一个无序数列：8，9，1，7，2，3，5，4，6，0使用希尔排序将其排列成一个从小到大的有序数列。

2.3 代码实现

package com.algorithm;

import java.util.Arrays;

/**
 * @author SnkrGao
 * @create 2023-04-15 15:03
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("排序前的数组为：");
        System.out.println(Arrays.toString(nums));

        shellSort(nums);

        System.out.println("排序后的数组为：");
        System.out.println(Arrays.toString(nums));
    }

    public static void shellSort(int[] nums) {

        // 增量gap初始为nums.length / 2，并逐渐减少，当gap == 1时执行最后一轮算法结束
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            // 下面的代码类比直接插入排序，原理是一致的，只是考虑gap增量，隔几个元素进行比较交换
            for (int i = gap; i < nums.length; i++) {
                int insertValue = nums[i];
                int insertIndex = i - gap;

                while (insertIndex >= 0 && insertValue < nums[insertIndex]) {

                    nums[insertIndex + gap] = nums[insertIndex];
                    insertIndex -= gap;
                }

                nums[insertIndex + gap] = insertValue;
            }
        }
    }
}

2.4 Shell Sort时间复杂度分析

可以看出Shell Sort的时间复杂度与gap增量序列的设计有很大关系，不同的gap序列对应着不同的时间复杂度，因此对其时间复杂度的分析非常复杂。

最好情况时间复杂度：O(n)

最坏情况时间复杂度：O(\(n^2\))

平均时间复杂度：O(\(nlong^2n\))