DevOps 插入排序

zijin5162 · November 10, 2019 · 12 hits
发表于:,更新于:2016-05-20,By Guodong

大纲

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

两张图


算法介绍

  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  {
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),稳定。

No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.