直接插入排序
空间复杂度O(1)
时间复杂度最好情况是O(n),最坏情况是O(n²),平均情况是O(n²)
是稳定的内排序算法

从后往前比较，把后面的元素作为哨兵

#include<iostream>
using namespace std;
#include<vector>


void InsertSort(vector<int> &q)
{
    for(int i = 1 ; i < q.size(); i++)
    {
        int t = q[i];
        int j;
        for(j = i - 1 ; j >=0 ; j--)
        {
            if(q[j] > t)
            {
                q[j+1] = q[j];
            }
            else
            {
                break;
            }
        }
        q[j+1] = t; 
    }
}

void DirectInsertSort(int a[],int n)
{
    for(int i = 1 ; i < n ; i++)
    {
        int t = a[i];
        int j;
        for(j = i - 1 ; j >= 0 ; j--)
        {
            if(a[j] > t)
            {
                a[j+1] = a[j];
            }
            else
            {
                break;
            }
        }
        a[j+1] = t;
    }
}

void InsertSort2(int a[],int n) //baike's solution
{
    int j;
    for(int i = 1 ; i < n ; i++)
    {
        if(a[i] < a[i-1])
        {
            int temp = a[i];
            for(j = i - 1; j >= 0 && a[j] > temp ; j--)
            {
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
}

void InsertSort_lts(vector<int> &q)
{
    for(int i = 1 ; i < q.size(); i++)
    {
        int t = q[i];
        int j;
        for(j = i - 1 ; j >=0 ; j--)
        {
            if(q[j] < t)
            {
                q[j+1] = q[j];
            }
            else
            {
                break;
            }
        }
        q[j+1] = t; 
    }
}

void DirectInsertSort_lts(int a[],int n)
{
    for(int i = 1 ; i < n ; i++)
    {
        int t = a[i];
        int j;
        for(j = i - 1 ; j >= 0 ; j--)
        {
            if(a[j] < t)
            {
                a[j+1] = a[j];
            }
            else
            {
                break;
            }
        }
        a[j+1] = t;
    }
}

void InsertSort2_lts(int a[],int n) 
{
    int j;
    for(int i = 1 ; i < n ; i++)
    {
        if(a[i] > a[i-1])
        {
            int temp = a[i];
            for(j = i - 1; j >= 0 && a[j] < temp ; j--)
            {
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
}

int main()
{
    int *arr = new int[10]{49,38,65,97,76,13,27,49};
    int n = sizeof(arr);
    //int arr[] = {49,38,65,97,76,13,27,49};
    //int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> a;
    for(int i = 0 ; i < n ; i++)
    {
        a.push_back(arr[i]);
    }

    InsertSort(a);
    for(auto i : a)
    {
        cout<<i<<" ";
    }
    cout<<endl;
    
    cout<<n<<endl;

    DirectInsertSort(arr,n);
    for(int i = 0 ; i < n ; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;

    int b[] = {8,6,4,9,7,1,2,5,0};
    int len = sizeof(b) / sizeof(b[0]);
    cout<<len<<endl;

    InsertSort2(b,len);
    for(int i = 0 ; i < len ; i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;

    InsertSort_lts(a);
    for(auto i : a)
    {
        cout<<i<<" ";
    }
    cout<<endl;

    DirectInsertSort_lts(arr,n);
    for(int i = 0 ; i < n ; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;

    InsertSort2_lts(b,len);
    for(int i = 0 ; i < len ; i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;


    system("pause");
    return 0;

}