关于java:持续输出面试题之插入排序篇

开篇介绍

大家好，我是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]);
    }

}

希尔排序

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

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

代码实现：

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;
    }
}