普林斯顿大学算法公开课笔记——插入排序

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。——极客学院

算法描述

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤 2~5

复杂度分析

  1. 时间复杂度:1/4 N^2的交换次数和比较次数

    • 在最坏情况下,数组完全逆序,插入第2个元素时要考察前1个元素,插入第3个元素时,要考虑前2个元素,……,插入第N个元素,要考虑前 N – 1 个元素。因此,最坏情况下的比较次数是 1 + 2 + 3 + … + (N – 1),等差数列求和,结果为 N^2 / 2,所以最坏情况下的复杂度为 O(N^2)。

    • 最好情况下,数组已经是有序的,每插入一个元素,只需要考查前一个元素,因此最好情况下,时间是线性的,时间复杂度为O(N)。

    • 插入排序的速度大约是选择排序的两倍

      排序算法的稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

  2. 空间复杂度分析

    算法所需的辅助空间是一个监视哨,辅助空间复杂度 S(n)=O(1)。是一个就地排序。

  3. 直接插入排序的稳定性

    直接插入排序是稳定的排序方法。

实例分析

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[5]   6   3   1   8   7   2   4
↑ │
└───┘
[5, 6] 3 1 8 7 2 4
↑ │
└────────┘
[3, 5, 6] 1 8 7 2 4
↑ │
└──────────┘
[1, 3, 5, 6] 8 7 2 4
↑ │
└──┘
[1, 3, 5, 6, 8] 7 2 4
↑ │
└────┘
[1, 3, 5, 6, 7, 8] 2 4
↑ │
└────────────────┘
[1, 2, 3, 5, 6, 7, 8] 4
↑ │
└─────────────┘

[1, 2, 3, 4, 5, 6, 7, 8]

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Insertion
{
public static void sort(Comparable[] a)
{
int N = a.length;
for(int i=1; i<N; i++)
for(int j=i; j>0;j--)
if(less(a[j],a[j-1]))
exch(a,j,j-1)
else break;
}
private static boolean less(Comparable v, Comparable w)
{
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a, int i, int j)
{
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
参考文献

常见排序算法 – 插入排序 (Insertion Sort)

直接插入排序