← 返回学习路线

SYSTEM

插入排序

Java基础插入排序system
src/content/notes/system/插入排序.md

插入排序

直接插入

插入排序(Insertion Sort):在要排序的一组数中,假定前 n-1 个数已经排好序,现在将第 n 个数插到这个有序数列中,使得这 n 个数也是排好顺序的,如此反复循环,直到全部排好顺序

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                // 比较索引j处的值和索引j-1处的值,
                // 如果索引j-1处的值比索引j处的值大,则交换数据,
                // 如果不大,那么就找到合适的位置了,退出循环即可;
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

插入排序时间复杂度:

  • 比较的次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
  • 交换的次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2
  • 总执行次数为:(N^2/2-N/2)+(N^2/2-N/2)=N^2-N

按照大 O 推导法则,保留函数中的最高阶项那么最终插入排序的时间复杂度为 O(N^2)


希尔排序

希尔排序(Shell Sort):也是一种插入排序,也称为缩小增量排序

实现思路:

  1. 选定一个增长量 h,按照增长量 h 作为数据分组的依据,对数据进行分组
  2. 对分好组的每一组数据完成插入排序
  3. 减小增长量,最小减为 1,重复第二步操作

希尔排序的核心在于间隔序列的设定,既可以提前设定好间隔序列,也可以动态的定义间隔序列,希尔排序就是插入排序增加了间隔

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        // 确定增长量h的初始值
        int h = 1;
        while (h < arr.length / 2) {
            h = 2 * h + 1;
        }
        // 希尔排序
        while (h >= 1) {
            // 找到待插入的元素
            for (int i = h; i < arr.length; i++) {
                // 把待插入的元素插到有序数列中
                for (int j = i; j >= h; j -= h) {
                    // 待插入的元素是arr[j],比较arr[j]和arr[j-h]
                    if (arr[j] < arr[j - h]) {
                        int temp = arr[j];
                        arr[j] = arr[j - h];
                        arr[j - h] = temp;
                    }
                }
            }
            // 减小h的值,减小规则为:
            h = h / 2;
        }
        System.out.println(Arrays.toString(arr));
    }
}

在希尔排序中,增长量 h 并没有固定的规则,有很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的,所以对于希尔排序的时间复杂度分析就认为 O(nlogn)