9.5 直接插入排序

2017-01-23 11:26:55.0

9.5.1 直接插入排序算法

    直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。

/* 插入排序 */
void InsertSort(SqList *L) 
{
    for(int i=2;i<=L->length;i++)//假设第一个位置是排序好的
    {   
        if(L->r[i]<L->r[i-1])//如果当前比前面的小,要插入到前面的某位置
        {   
            L->r[0]=L->r[i];//设置哨兵
            int j;
            for(j=i-1;L->r[j]>L->r[0];j--)
            {   
                L->r[j+1]=L->r[j];//把大于当前元素的那些往后移
            }   
            L->r[j+1]=L->r[0];//找到合适位置插入
        }   
    }   
}                                                             

9.5.2 直接插入排序复杂度分析

    最好的情况,序列本身是有序的,则只需要比较不需要移动。最坏的情况,即逆序时,比较次数为:次。而移动次数也最大为:次。

    总的来说,比较和移动次数约为n2/4。因此得出直接插入排序的时间复杂度也是O(n2)。同样为O(n2),直接插入排序比冒泡(大约为n2/2)和简单选择(大约为n2/2)的性能要好些。