1. 从第一个元素开始，这个元素可以认为已经被排序；
2. 取出下一个元素a[i]，按照从后往前的速度开始扫描；
3. 如果当前的元素值比a[i]小，则将该元素下移一位；
4. 如果当前的元素值比a[i]大，则将a[i]放到此元素的下一个位置；
5. 重复步骤2，直到完成所有的元素的排序。

//插入排序

void InsertionSort(int a[], int length)

{

    //排序序列中的第i个元素,i属于[1,2,...,n]的区间

    for(int i = ; i <= length; i++)

    {

        int temp = a[i];

        //a[1],a[2],...,a[i-1]序列是有序的，插入a[i]

        for(int j = i- ; j >= -; j--)

        {

            if( a[j] <= temp)

            {

                //将第j-1的元素赋值给第j位

                a[j+] = a[j];

            }

            //完成排序的条件：1.a[j]>temp;2.j移动到-1的位置

            if( a[j] > temp || j < )

            {

                //排序完毕，将temp赋值给a[j+1]

                a[j+] = temp;

                break;

            }

        }

    }

}