插入排序

原理

• 将待排列元素划分为已排序和未排序两部分，每次从未排序的元素中选择一个插入到已排序的元素中的正确位置

• 类似于打扑克时的抓牌

  性质

• 稳定性：稳定的

• 时间复杂度：
  • 最优：
  • 平均和最坏：

    代码

    public void insertion_sort(int[] a) {
    for (int i = 1; i < a.length; i++) {
       int key = a[i];
       int j = i - 1;
       while (j >= 0 && a[j] > key) {
           a[j + 1] = a[j];
           j--;
       }
       a[j + 1] = key;
    }
    }