一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置中
6. 重復(fù)步驟2~5

具體C++源代碼如下：

#include <iostream>
using namespace std;

/**///////////排序后輸出函數(shù)
bool Output(int b[],int length)
{
    for (int i=0;i<length;i++)
    {
        cout<<b[i]<<"  ";
    }
    cout<<endl;
    return true;
}

/**///////////插入排序
void InsertionSort(int arr[],int size_arr)
{
    for (int i=1;i<size_arr;i++)
    {
        int key=arr[i];
        int j=i;
        while((j>0) && (arr[j-1]>key))
        {
            arr[j]=arr[j-1];   //交換順序
            --j;
        }
        arr[j]=key;
    }
}
void main()
{
    //動(dòng)態(tài)輸入待排序數(shù)組
    int size_a;
    cout<<"Enter the numble of a: size_a=";
    cin>>size_a;
    cout<<endl<<"Enter a(size_a values):";
    int* a=new int[size_a];
    for (int i=0;i<size_a;i++)
    {
        cin>>a[i];
    }

    cout<<endl<<"former:"<<endl;
    Output(a,size_a);
    cout<<endl<<"later:"<<endl;

    //調(diào)用插入排序
    cout<<"插入排序:";
    InsertionSort(a,size_a);
    Output(a,size_a);
}