数据结构-直接插入排序-带哨兵解法 （C++描述）

1.带哨兵的直接插入排序

#include <iostream>
using namespace std;
int f(int a[],int n){
    int i,j;
    for( i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            //将要插入的值赋值给哨兵
            a[0]=a[i];
            a[i]=a[i-1];
            //小于哨兵的向后挪一位
            for( j=i-2;a[j]>a[0];j--)
                a[j+1]=a[j];
            //排序值插入
            a[j+1]=a[0];
        }
    }
}
int main(){
    int n;
    //a[]的最大值不要设置100，否则会出现 运行错误
    int a[1000];
    cin>>n;
    //a[0]空出来设置哨兵
    for(int i=1;i<=n;i++)
        cin>>a[i];
    //调用插入排序函数
    f(a,n);
    //输出排序后的数列
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

2.不带哨兵的直接插入排序

#include <iostream>
using namespace std;
int f(int a[],int t,int n,int N){
    for(int i=0;i<n;i++){
        //某个位置的数大于待排序数，则剩下的数向后移一位
        if(a[i]>t){
            for(int j=N-1;j>=i;j--)
                a[j]=a[j-1];
            //插入待排序数
            a[i]=t;
            return 0;
        }
    }
    //找不到比其小的数，则插在最后一位
    a[n]=t;
    return 0;
}
int main(){
    int N;
    cin>>N;
    //a[]的最大值不要设置100，否则会出现 运行错误
    int a[1000];
    //数组初始化
    for(int i=0;i<N;i++)
        a[i]=0;
    //输入第一数
    cin>>a[0];
    //插入一个排序一个
    for(int i=1;i<N;i++){
        int t;
        cin>>t;
        f(a,t,i,N);
    }
    //输出结果
    for(int i=0;i<N;i++)
        cout<<a[i]<<" ";
    return 0;
}