插入排序
最近无聊在啃算法导论，里面的东西有点难懂，隔三差五就是一串英文。所以准备讲解一下里面的东西。
第一个算法就是“插入排序”。伪代码如下：
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++代码后是这样：
#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一步一步移到它该在的位置。最后，跳出循环，收工走人。
时间复杂度
显而易见，这个算法的时间复杂度为：
（本章完）
