image.png
    要求

    • 能够用自己语言描述插入排序算法
    • 能够比较插入排序与选择排序

    算法描述

    1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）
    2. 重复以上步骤，直到整个数组有序

    算法实现

    1. public static void insert(int []a){
    2.         for (int i = 1; i < a.length; i++) {
    3.             for(int j=i;j>0;j--){
    4.                 if (a[j]<a[j-1]){
    5.                     swap(a,j,j-1);
    6.                 }else{
    7.                     break;
    8.                 }
    9.             }
    10.         }
    11.     }

    另一种

    1. // 修改了代码与希尔排序一致
    2. public static void insert(int[] a) {
    3.     // i 代表待插入元素的索引
    4.     for (int i = 1; i < a.length; i++) {
    5.         int t = a[i]; // 代表待插入的元素值
    6.         int j = i;
    7.         while (j >= 1) {
    8.             if (t < a[j - 1]) { // j-1 是上一个元素索引，如果 > t，后移
    9.                 a[j] = a[j - 1];
    10.                 j--;
    11.             } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
    12.                 break;
    13.             }
    14.         }
    15.         a[j] = t;
    16.         System.out.println(Arrays.toString(a) + " " + j);
    17.     }
    18. }

    与选择排序比较

    1. 二者平均时间复杂度都是 O(n^2)
    2. 大部分情况下，插入都略优于选择
    3. 有序集合插入的时间复杂度为 O(n)
    4. 插入属于稳定排序算法，而选择属于不稳定排序