最近做一个排序中间件，所以需要研究排序算法，而且重点是要实现出来。
实现算法语言为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 ，如需转载请自行联系原作者
