持续输出面试题之插入排序篇

开篇介绍

大家好，我是Java最全面试题库的提裤姐，今天这篇是数据结构与算法篇，主要介绍插入排序；在后续，会沿着第一篇开篇的知识线路一直总结下去，做到日更！如果我能做到百日百更，希望你也可以跟着百日百刷，一百天养成一个好习惯。

插入排序

插入排序的基本思想是：每次将一个待排序的记录按其关键字的大小插入到前面已排好序的文件中的适当位置，直到全部记录插入完为止。插入排序主要包括直接插入排序和希尔排序两种。

直接插入排序

每次从无序区取出第一个元素把它插入到有序区的适当位置，使之成为新的有序区，经过n-1次插入后完成。
时间复杂度：最好是O(n)，最坏是O(n^2)
空间复杂度：O(1)
属于稳定算法。
代码示例：

/**
 * 直接插入排序
 *
 * @param arrays 需要排序的序列
 */
public static void sort(int[] arrays) {
    if (arrays == null || arrays.length == 0) {
        return;
    }
    //辅助序列
    LinkedList<Integer> list = new LinkedList<Integer>();
    //取出无序序列的第一个元素
    list.add(arrays[0]);
    //从第二个元素依次遍历，放入辅助序列（有序）的合适位置
    for (int index = 1; index < arrays.length; index++) {
        for (int listIndex = 0; listIndex < list.size(); listIndex++) {
            //一直遍历，直到找到比自己大的数，放在这个数前面
            if (arrays[index] < list.get(listIndex)) {
                list.add(listIndex, arrays[index]);
                break;
            }
            //如果遍历到末尾还没有找到比自己大的数，直接放最后一个位置
            if (listIndex == list.size() - 1 && list.get(listIndex) < arrays[index]) {
                list.add(arrays[index]);
            }
        }
    }
    for (int i = 0; i < list.size(); i++) {
        arrays[i] = list.get(i);
    }
}


public static void main(String[] args) {
    int[] array = new int[]{9, 3, 8, 7, 4, 5, 1};
    sort(array);

    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }

}

希尔排序

又叫缩小增量排序，把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入排序进行排序；小组的个数逐次缩小，当完成了所有的数据元素都在一个小组内的排序后，排序过程结束。所以希尔排序又称作缩小增量排序。

希尔排序示例.png

希尔排序的前提是在直接插入排序之上，是对直接插入排序的一个升级版。属于不稳定算法。

代码实现：

public static void shellSort(int[] arr) {

    //初始化增量
    int h = 1;
    //计算最大间隔，公式：h = h * 3 + 1
    while (h < arr.length / 3) {
        h = h * 3 + 1;
    }
    //缩小增量进行排序
    while (h > 0) {
        //进行插入排序
        //等待插入的数
        int waitInsert;
        //i表示当前待插入数下标；j表示本次被比较的有序数位置
        int i, j;
        for (i = h; i < arr.length; i++) {
            //得到本轮待插入的数
            waitInsert = arr[i];
            //比较位置初始化，也就是有序序列的最后一个位置，从后往前
            j = i - h;

            //若大于或等于等待插入的数值大小，则该数右移一个间隔大小，然后进行下一次比较
            while (j > -1 && arr[j] >= waitInsert) {
                arr[j + h] = arr[j];
                j = j - h;
            }
            //插入的位置一定是上一次比较的数的位置，也就是j+h的位置。（注意到j-h的时机即可理解）
            arr[j + h] = waitInsert;
        }
        //缩小增量，公式：h = (h - 1) /3
        h = (h - 1) / 3;
    }
}