#include<iostream>//时间复杂度O(n^2) 
#include<malloc.h>
using namespace std;
void InsertSort(int *&,int);//直接插入排序。 
int main(void)
{
    int len;
    cout<<"请输入长度：";
    cin>>len;cout<<endl;
    int *pArr=(int *)malloc(sizeof(int)*len);
    cout<<"请输入数值：";
    for(int i=0;i<len;i++)
    {
        cin>>pArr[i];
     }
     cout<<"排序前：";
    for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl;cout<<"排序后：";
     InsertSort(pArr,len);
     for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl; 
    
    return 0;
}
/*void InsertSort(int* &s,int len)//我的方法 
{
    int i,j;
    for(i=1;i<len;i++)//下标从0开始 
    { 
        int t=i; 
        int j=i-1;//确定前面已排序最后一位下标 
        if(j>=0&&s[j]>s[t])
        {
            for(j;s[j]>s[t]&&j>=0;j--,t--)
            {
                int key=s[t];//相当于临时变量
                s[t]=s[j];
                s[j]=key;
            }   
        }   
    } 
}*/
void InsertSort(int* &s,int len) 
{
        for(int i=1;i<len;i++){
                int key=s[i];
                int j=i-1;
                while((j>=0) && (key<s[j])){
                        s[j+1]=s[j];
                        j--;
                }
                s[j+1]=key;
        }

}