数据结构教程第三十七课实验八排序实验

文章作者 100test 发表时间 2007:03:10 18:28:13
来源 100Test.Com百考试题网

教学目的： 掌握简单插入排序、快速排序、堆排序的算法并加以应用。
教学重点：
教学难点：
授课内容：
实现下述三种算法，并用以下无序序列加以验证：
49，38，65，97，76，13，27，49
一、简单插入排序
二、快速排序
三、堆排序
以上算法的C源程序。
#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType.
typedef int InfoType.
typedef struct{
KeyType key.
InfoType otherinfo.
}RedType.
typedef struct{
RedType r[MAXSIZE 1].
int length.
}SqList.

void InsertSort(SqList *L)
{
int i,j.
for(i=2.i<=L->length. i)
if(LT(L->r[i].key,L->r[i-1].key)){
L->r[0]=L->r[i].
for(j=i-1. LT(L->r[0].key,L->r[j].key). --j)
L->r[j 1]=L->r[j].
L->r[j 1]=L->r[0].
}
}

void BInsertSort(SqList *L)
{
int i,j.
int low,high,m.
for(i=2.i<=L->length. i){
L->r[0]=L->r[i].
low=1.high=i-1.
while(low<=high){
m=(low high)/2.
if (LT(L->r[0].key,L->r[m].key))
high=m-1.
else low=m 1.
}
for(j=i-1.j>=high 1.--j)
L->r[j 1]=L->r[j].
L->r[high 1]=L->r[0].
}
}