插入排序是一个就地算法，所以空间用量是一个常量。
处理的第一个元素是下标为1的元素。第一个元素无需处理。

排序思路:

就像抓取一幅扑克牌，将桌上的扑克牌抓在左手上，第一张抓到左手上的牌是必然有序的，从第二张牌开始，每抓取一张牌都要和左手上的牌从右边开始，逐一比对大小，如果大于某张牌，则插入到这张牌的后面

伪代码

  1.         /*
  2.          *
  3.          * for j=2 to A.length
  4.          *     key = A[j]
  5.          *     i = j - 1
  6.          *     while i > 0 and A[i] > key
  7.          *         A[i+1] = A[i]
  8.          *         i = i - 1
  9.          *     A[i+1] = key
  10.          *
  11.          * */

Java代码实现

  1.         int[] arr = {31, 41, 59, 26, 41, 58};
  2.         int key, i;
  3.         for (int j = 1; j < arr.length; j++) {
  4.             key = arr[j];
  5.             i = j - 1;
  6.             while (i >= 0 && arr[i] > key) {
  7.                 arr[i + 1] = arr[i];
  8.                 i--;
  9.             }
  10.             arr[i + 1] = key;
  11.         }
  12.         System.out.println(Arrays.toString(arr));

循环不变式：v[0] … v[i-1] 当前已排序，保留原有数据

  • 初始化：v[0]有序
  • 维护不变式：v[0] … v[i-1]有序 —-> v[0] … v[i]有序
  • 终结：v[0] … v[v.size() - 1]有序

插入排序分析：

运行时间：元操作的运行次数。
一句代码的运行时间为一个常数

输入规模量

输入形态：
最好情况和最坏情况。一般关注的是最坏情况。

最好：O(n) 最坏：O(n^2)