插入排序

发表于:，更新于:，By Guodong
大纲
  1. 1. 两张图
  2. 2. 算法介绍
  3. 3. 代码实现
  4. 4. 时间复杂度

打过扑克吗？一般情况从抓牌开始到最后，你手里的牌已经按顺序排好了，这就是插入排序。

两张图


算法介绍

  1. index=2；
  2. 从第index个元素开始遍历，当前元素为key；
  3. 将key向左移动，直至左侧数字不大于key；
  4. index++；
  5. index不超过数组大小，返回2；超过数组大小，排序结束。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Sort {
    public static void insertionSort(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;
        }
    }
}

时间复杂度

最好o(n)，最差o(n^2)，平均o(n^2)，空间复杂度o(1)，稳定。