代码

第一个算法就是“插入排序”。伪代码如下：

1
2
3
4
5
6
7
8
9
def INSERTION_SORT(var A[]):
    var i,j,key;
    for i=2 to A.length-1:         //A.length返回数列以“1”开始时的长度，我们需要-1
        key = A[i];
        j = i-1;
        while j>-1 and A[j]>key:   //算法导论中原是“while i>0 and A[i]>key”
            A[j+1]=A[j];
            j-=1;
        A[j+1]=key;

转换成C++代码后是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main() {
    int a[10]={0};
    int i,j,key;
    int n;
    cin >> n;
    for (i=0;i<n;i++)
     cin >> a[i];
    for (i=1;i<n;i++) {
        key=a[i];
        j=i-1;
        while (j>-1 && a[j]>key) {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }
    for (i=0;i<n;i++)
     cout << a[i];
    return 0;
}

算法分析

先定义两个循环变量：i，j。还有每次循环的key，也就是基准数。

接着可以从2循环到数列结尾了。我们假设a[0]~a[i]已经排好序，基准数key就是这次循环时的i，j即是i-1。

接下来再加入一层循环，这层循环的作用是把基准数key挪到正确位置，该循环在j索引比数列最小索引小，且key比j代表的数小时跳出（key比A[j]小代表着基准数的位置过了，所以跳出循环后要把key挪到j+1的位置）。

第二层循环中，j每次-1，A[j+1]转换成A[j]，为的是将基准数key一步一步移到它该在的位置。最后，跳出循环，收工走人。

时间复杂度

显而易见，这个算法的时间复杂度为：

$$ \theta(N^2) $$

（本章完）