插入排序算法

以递增或递减的顺序对数字进行排序是一种非常简单的方法。

它具有各种优点：

1. 实现起来很简单。
2. 它对小型数据集有效。
3. 它是稳定的（不更改具有相同键的元素的相对顺序）
4. 它就位（仅需要恒定数量的O（1）的额外存储空间）。
5. 这是一种在线算法, 因为它可以在收到列表时对其进行排序。

ALGORITHM: INSERTION SORT (A)
1. For k ← 2  to length [A]
2. Do key ← A[k]
3. i=k-1
4. while i>0 and A[i]>key
5. do A[i+1] ← A[i]
6. i=i-1
7. A[i+1] ← key

分析

1. 输入：给出n个元素。
2. 输出：进行排序所需的比较数。
3. 逻辑：如果我们在插入排序中有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 [] =

对于j = 2到5

J=2, key=A [2]
        Key=15
I=2-1=1, i=1
While i>0 and A [1]>15
A Condition false, so no change
Now=3, key=A [3] =7
I=3-1=2
I=2, key=7
While i>0 and A [2]>key 
Condition is true
So A [2+1] ← A [2]
      A [3] ← A [2]

即

and i=2-1=1, i=1
while i>0 and A [1]>key
A Condition false. So no change
Then A [1+1] ← key
    A [2] ← 7

那是

For j=4
Key=A [4]
Key = 18, i=3
Now, while 3>0 and A [3]>18
The Condition is false, No change.
Similarly, j=5    
      Key=A [5]
So key=16, i=4
Now while 4>0 and A [4]>16
Condition is true
 So A [5] =16 and i=4-1=3
Now while 3>0 and A [3]>16
Condition is false
So A [3+1] =A [4] =16

排序后的数组是：