最近做一个排序中间件,所以需要研究排序算法,而且重点是要实现出来。
实现算法语言为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;
}
测试
为了便已测试,下面给一个完整的测试代码
插入排序算法实例
关于插入排序的效率
空间: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
本文转自 Ron Ngai 博客园博客,原文链接:http://www.cnblogs.com/rond/archive/2012/04/16/2452729.html ,如需转载请自行联系原作者