• 将待排序数组分为有序数组和无序数组，有序数组初始为数组的一个元素（只有一个元素的数组肯定是有序的）。每轮排序从无序数组中取出一个数字插入到有序数组里，从而成为一个更长的有序数组，最后完成排序。
    • 稳定排序。
    • 在接近有序的情况下，表现优异。
      1.   public static void insertSort(int[] arr) {  //基于赋值
      2.       for (int i = 1; i < arr.length; i++) {
      3.           int ai = arr[i];
      4.           int j=i;
      5.           if (ai < arr[j - 1]) {
      6.               while (j > 0 && arr[j-1] > ai) {  //将arr[i]插入到arr[0,i)的合适位置
      7.                   arr[j] = arr[j-1];
      8.                   j--;
      9.               }
      10.               arr[j] = ai;
      11.           }
      12.       }
      13.   }