内部排序——直接插入排序

最近做一个排序中间件,所以需要研究排序算法,而且重点是要实现出来。

实现算法语言为C语言,使用环境为VS2010集成环境。

待排记录数据类型:

//数据
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct{
    KeyType key;            //关键字项
    InfoType otherinfo;        //其他数据项
}RedType;                    //记录类型
typedef struct{
    RedType r[MAXSIZE+1];    //r[0]闲置或用作哨兵单元
    int length;                //顺序表长度
}SqList;                    //顺序表类型

最简单的插入排序

直接插入排序:将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数字增1的有序表

直接插入排序理论比较简单,算法也比较简单。

//插入排序
void InsertSort(SqList &L){
    //对顺序表L作直接插入排序
    for(int i=2;i<=L.length;i++){
        if(LT(L.r[i].key,L.r[i-1].key)){
            L.r[0]=L.r[i];
            L.r[i]=L.r[i-1];
        }
        int j=i-2;
        for(;LT(L.r[0].key,L.r[j].key);j--){
            L.r[j+1]=L.r[j];
        }
        L.r[j+1]=L.r[0];
    }
}

函数LT(int,int)是比较的内容。根据数据类型比较,这里有一个整型大小比较的例子。

bool LT(int x,int y){
    if(x<y)
        return true;
    else
        return false;
}

测试

为了便已测试,下面给一个完整的测试代码

插入排序算法实例
// TestInserSort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdio.h"

//数据
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct{
    KeyType key;            //关键字项
    InfoType otherinfo;        //其他数据项
}RedType;                    //记录类型
typedef struct{
    RedType r[MAXSIZE+1];    //r[0]闲置或用作哨兵单元
    int length;                //顺序表长度
}SqList;                    //顺序表类型


bool LT(int x,int y){
    if(x<y)
        return true;
    else
        return false;
}
//插入排序
void InsertSort(SqList &L){
    //对顺序表L作直接插入排序
    for(int i=2;i<=L.length;i++){
        if(LT(L.r[i].key,L.r[i-1].key)){
            L.r[0]=L.r[i];
            L.r[i]=L.r[i-1];
        }
        int j=i-2;
        for(;LT(L.r[0].key,L.r[j].key);j--){
            L.r[j+1]=L.r[j];
        }
        L.r[j+1]=L.r[0];
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    SqList L;
    scanf("%d",&L.length);
    for(int i=1;i<=L.length;i++){
        scanf("%d",&L.r[i].key);
    }
    InsertSort(L);
    for(int i=1;i<=L.length;i++){
        printf("%d\t",L.r[i].key);
    }
    return 0;
}

关于插入排序的效率

空间:S(1),直接插入排序只需要一个辅助空间。

时间:排序的基本炒作为,1.比较关键字的大小;2.移动记录

最好情况:当记录已经是有序而且序列就是所求顺序的时候,第二个for循环将不会被运行,整体空间复杂度为O(n)

最坏情况:当记录和需要得出的序列刚好相反时,第二个for循环被执行的次数最多,比较次数为(2,3,...,n)次,即(n+2)(n-1)/2,移动次数为(2,3,...,n,n+1),即(n+4)(n-1)/2。

平均次数大约为n2/4,即时间复杂度为O(n2)

 

 

参考资料
[1] 严蔚敏 吴伟民 《数据结构(C语言版)》 北京:清华大学出版社,1997.4
原文地址:https://www.cnblogs.com/rond/p/2452729.html