[数据结构与算法]插入排序算法

插入排序的核心思想是：
1 向一个已有序的队列中插入数据，
n个数，那么只需要插入n-1次

实现如下：
将第一个数看作一个自然有序的队列.

#include <iostream>
#include <algorithm>
using namespace std;
void InsertSoft(int* a,int length)
{
    if(a != NULL && length > 0)
    {
        for(int i = 1;i < length;i++)
        {
            int curValue = a[i];
            int prevIndex = i - 1;
            while(curValue < a[prevIndex] && prevIndex > 0)
            {
                a[prevIndex + 1] = a[prevIndex];
                prevIndex--;
            }
            a[prevIndex + 1] = curValue;
        }
    }
}
int main()
{
	int a[] ={0,1,2,65,54,20,30,40,20};
	int lengthA = sizeof(a) / sizeof(a[0]);
    InsertSoft(a,lengthA);
 	std::for_each(a,a+lengthA,[](int i){
 	    std::cout << i << std::endl;});
	return 0;
}

注：插入排序是稳定排序，因为在排序过程中，相同值的相对大小关系未发生改变。
外层循环控制将要插入的数据，内层循环控制，比较和移动。