以递增或递减的顺序对数字进行排序是一种非常简单的方法。
它具有各种优点：
- 实现起来很简单。
- 它对小型数据集有效。
- 它是稳定的（不更改具有相同键的元素的相对顺序）
- 它就位（仅需要恒定数量的O（1）的额外存储空间）。
- 这是一种在线算法, 因为它可以在收到列表时对其进行排序。
ALGORITHM: INSERTION SORT (A)1. For k ← 2to length [A]2. Do key ← A[k]3. i=k-14. while i>
0 and A[i]>
key5. do A[i+1] ← A[i]6. i=i-17. A[i+1] ← key分析
- 输入：给出n个元素。
- 输出：进行排序所需的比较数。
- 逻辑：如果我们在插入排序中有n个元素, 则需要n-1次通过才能找到排序后的数组。
In pass 1: no comparison is required In pass 2:1 comparison is required In pass 3: 2 comparisons are required........................................................................................................................................................... In pass n: n-1 comparisons are required Total comparisons: T (n) = 1+2+3+...........+ n-1= = o (n2)Therefore complexity is of order n2例：
说明在数组A =（4、15、7、18和16）上进行INSERTION SORT的操作。
解：
A [] =
| 4 | 15 | 7 | 18 | 16 |
J=2, key=A [2]Key=15I=2-1=1, i=1While i>
0 and A [1]>
15A Condition false, so no changeNow=3, key=A [3] =7I=3-1=2I=2, key=7While i>
0 and A [2]>
key Condition is trueSo A [2+1] ← A [2]A [3] ← A [2]即
| 4 | 15 | 18 | 16 |
and i=2-1=1, i=1while i>
0 and A [1]>
keyA Condition false. So no changeThen A [1+1] ← keyA [2] ← 7那是
| 4 | 7 | 15 | 18 | 16 |
For j=4Key=A [4]Key = 18, i=3Now, while 3>
0 and A [3]>
18The Condition is false, No change.Similarly, j=5Key=A [5]So key=16, i=4Now while 4>
0 and A [4]>
16Condition is true So A [5] =16 and i=4-1=3Now while 3>
0 and A [3]>
16Condition is falseSo A [3+1] =A [4] =16【插入排序算法】排序后的数组是：
| 4 | 7 | 15 | 16 | 18 |
