直接插入排序算法

 一种简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表

#include<iostream>
    using namespace std;
    int main()
    {
        int a[]={98,76,109,34,67,190,80,12,14,89,1};
        int k=sizeof(a)/sizeof(a[0]);
        int i,j;
        for(i=1;i<k;i++)//循环从第2个元素开始
        {
            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;//此处就是a[j+1]=temp;
            }
        }
        for(int f=0;f<k;f++)
        {
            cout<<a[f]<<"  ";
        }
        return 0;
    }

特性
1.时间复杂度
最好情况就是全部有序，此时只需遍历一次，最好的时间复杂度为O ( n ) O(n)O(n)
最坏情况全部反序，内层每次遍历已排序部分，最坏时间复杂度为O ( n 2 ) O(n^2)O(n 
2
)

综上，因此直接插入排序的平均时间复杂度为O ( n 2 ) O(n^2)O(n 
2
)

2.空间复杂度
辅助空间是常量
平均的空间复杂度为：O ( 1 ) O(1)O(1)