直接插入排序（插入排序）

1.基本代码
2.优化代码
3.算法分析

基本思想：

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

(即边插入边排序，保证子序列中随时都是排好序的)

Screen Shot 2018-12-18 at 20.25.27.png

#include<iostream>
using namespace std;
int main()
{
    int n=6,a[6]={21,25,49,25,16,8};//定义 n为整数，a为整数组
    for(int i=2,j,t;i<=n;i++)       //趟数i=n-1
    {
        for(j=i-2,t=a[i-1];j>=0;j--)    //比较次数不确定，用t存a[i-1]
        {
            if(a[j]>t)      //如果前面的数比后面的大
            {
                a[j+1]=a[j];    //往后移动
            }
            else
            {
                break;
            }   
        }
        a[j+1]=t;//a[j+1]存a[i-1]
        
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";//8 16 21 25 25 49
    return 0;
}

#include <iostream>
using namespace std;
#define N 2
int main(int argc, const char * argv[]) {
    // insert code here...
    int A[N]={3,1};
    int i,x,j;
    for(i=1;i<N;i++){
        x=A[i];
        for(j=i-1;j>=0;j--){
            if(A[j]>x){
                A[j+1]=A[j];
            }else{
                break;
            }
        }
        A[j+1]=x;
    }
    for(i=0;i<N;i++)
        cout<<A[i]<<" ";
    return 0;
}

优化代码

void InsertSort(SqList ＆L)
 {int i,j;
   for(i=2;i<=L.length;++i)
     if( L.r[i].key<L.r[i-1].key)//将L.r[i]插入有序子表
       { L.r[0]=L.r[i]; // 复制为哨兵
          L.r[i]=L.r[i-1];
          for(j=i-2; L.r[0].key<L.r[j].key;--j)
                L.r[j+1]=L.r[j]; // 记录后移 
         L.r[j+1]=L.r[0]; //插入到正确位置
       }
 }

算法分析

设对象个数为n，则执行n-1趟比较次数和移动次数与初始排列有关
最好情况下： 每趟只需比较 1 次，不移动。 总比较次数为 n-1
最坏情况下：第 i 趟比较i次，移动i+1次

Screen Shot 2018-12-18 at 21.29.37.png

若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况平均情况比较次数和移动次数为n2/4

时间复杂度为 o(n2)
空间复杂度为 o(1)
是一种稳定的排序方法