插入排序
1、基本思路
对于一个数组A，依次取出元素，设想（其实是在A中）放到数组B中（B最初没有元素，为空数组），将取出的元素依次与B中的元素比较，选取合适的位置插入，最终完成排序。
伪代码为：
insertion-sort(A)
for j=2 to length[A]
key = A[j]
// insert A[j] into sorted A[1,2,...,J-1]
i = j-1
while i>0 && A[i]>key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
2、C++代码
void InsertionSort(int* A, int length)
{
for (int j = 1; j < length; ++j)
{
int key = A[j];
int i = j - 1;
while (i >= 0 && A[i] > key)
{
A[i + 1] = A[i];
i = i - 1;
}
A[i + 1] = key;
}
}
int main()
{
int A[5] = { 5,4,2,3,1};
int length = 5;
InsertionSort( A, length);
return 0;
}
