【算法导论】插入排序法

插入排序法的时间复杂度为n的平方，对于较小的输入规模来说，插入排序法比合并排序法更快些。在最佳情况下，即输入数组已经排序好，则时间复杂度可表示为n,是一个线性函数；在最差情况下，即输入数组是逆序排列时，时间复杂度为 $an^2+bn+c$. 插入排序法的具体实现方法如下：

具体的c/c++语言实现如下：

c/c++语言实现：

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

void InsectionSortAscend(int* arrayA,int Length);//插入排序法：升序
void InsectionSortDescend(int* arrayA,int Length);//插入排序法：降序

void main()
{
    clock_t start,finish;
    double totaltime;
    start=clock();

    int arrayA[6]={5,2,4,6,1,3};
    int Length=sizeof(arrayA)/sizeof(int);

    InsectionSortDescend(arrayA,Length);
    InsectionSortAscend(arrayA,Length);
    
    finish=clock();
    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"此两个程序的运行时间为"<<totaltime<<"秒！"<<endl;
    
}
/*****************************************
/            插入排序
/输入：数组arrayA、数组长度
/输出：由小到大已排列好的数组
/时间复杂度：n的平方
/*****************************************/
void InsectionSortAscend(int* arrayA,int Length)
{
    int i=0;
    int j=0;
    int temp=0;
    
    for(i=1;i<Length;i++)
    {
        temp=arrayA[i];
        j=i-1;
        while(j>=0&&arrayA[j]>temp)
        {
            arrayA[j+1]=arrayA[j];
            j=j-1;
        }
        arrayA[j+1]=temp;
    }
    for(int i=0;i<Length;i++)
       cout<<arrayA[i];
    cout<<endl;

}

/*****************************************
/            插入排序
/输入：数组arrayA、数组长度
/输出：由大到小已排列好的数组
/时间复杂度：n的平方
/*****************************************/
void InsectionSortDescend(int* arrayA,int Length)
{
    int i=0;
    int j=0;
    int temp=0;
    
    for(i=Length-2;i>=0;i--)
    {
        temp=arrayA[i];
        j=i+1;
        while(j<Length&&arrayA[j]>temp)
        {
            arrayA[j-1]=arrayA[j];
            j=j+1;
        }
        arrayA[j-1]=temp;
        
    }
    for(int i=0;i<Length;i++)
       cout<<arrayA[i];
    cout<<endl;

}