• 要求
• 算法描述
• 算法实现
• 与选择排序比较
• 提示

要求

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

  算法描述

1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）

2. 重复以上步骤，直到整个数组有序

   算法实现

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

   与选择排序比较

3. 二者平均时间复杂度都是 #card=math&code=O%28n%5E2%29&id=tvWrO)

4. 大部分情况下，插入都略优于选择
5. 有序集合插入的时间复杂度为 #card=math&code=O%28n%29&id=qbdmN)
6. 插入属于稳定排序算法，而选择属于不稳定排序

   提示

插入排序通常被同学们所轻视，其实它的地位非常重要。小数据量排序，都会优先选择插入排序