[Day17] CH10：排序大家族——插入排序法

今天第三天要登场的是插入排序法（Insertion Sort），我自己在玩扑克牌的时候，都是使用这种排序，不知道你们是不是也是呢？

插入排序法

将资料分成已排序与未排序，由未排序的第一笔资料开始，插入到已排序资料的适当位置，插入时由後至前比较，直到遇到比当前资料 (temp) 小的值再插入，比较时若遇到比 temp 大或相等，则往後移。

给定一个阵列：

41, 24, 97,  6, 19, 53, 78

首先，24 比 41 小插入到 41 前

24, 41, 97,  6, 19, 53, 78

接下来 97 比 41 大，插入 41 後面

24, 41, 97,  6, 19, 53, 78

再来，6 比 24 小，插入到 24 前

 6, 24, 41, 97, 19, 53, 78

以此类推，最後 78 插入完就完成排序，以下是动图与程序法：

插入排序法动图

public class InsertionSort {
    public static void main(String[] args){
        int[] arr = {41, 24, 97, 6, 19, 53, 78};
        int n = arr.length;
        for(int i = 1 ; i < n ; i++){
            int temp = arr[i];
            int j = i-1;
            while(j >= 0 && arr[j] > temp){ //持续比对是否比 temp 大
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        for(int i = 0 ; i < n ; i++){
            System.out.printf("%d ", arr[i]);
        }
    }
}

时间复杂度

在最佳的情况下，也就是一开始便由小到大排序，因此只需走过阵列长度的次数，每一次只需 1 个步骤（都不需移动），时间复杂度为 O(n)。而在最坏的情况，阵列一开始由大到小排序，每一次需要 i 个步骤，总共会需要和选择排序法一样的 n * (n + 3) / 2，时间复杂度为 O( $n^2$ )。平均的话，每一次会需要比较 n / 2 个数字，总共 n 次，所以时间复杂度一样为 O( $n^2$ )。