准备m个箱子，先按低位分箱再按序号一次将各个非空箱子里的记录收集起来，再对新收集起来的元素依次按较高的位分箱，直到最高位。
分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。
按最高位分箱后，按序号一次将各个非空箱子里的记录收集起来，得到的元素序列就是有序的。
Hash排序是在Hash查找的基础上演变而来。
对待排序列采用单调的Hash函数，并用链地址法处理冲突，最后用一定规则收集存储好的数据从而得到有序序列。
3、主要仪器设备及耗材
安装有VC++6.0运行环境的电脑，无耗材要求。
4、实验方案或技术路线
本实验含有五部分内容——静态查找、动态查找、插入排序与选择排序、快速排序与归并排序、查找及排序算法集成。
A．静态查找部分
查找表的存储结构为有序表，即表中记录按关键字大小排序存放。
输入待查数据元素的关键字进行查找。
为了简化算法，记录只含一个整型量关键字字段，记录的其余数据部分忽略不考虑。
此程序中要求对整型量关键字数据的输入按从小到大排序输入。
B．动态查找部分
主要的功能是查找，查找表为高校最低录取分数信息的集合。
根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。
为了提高查询速度，可建立二叉排序树并在二叉排序树中实现查找。
C．排序部分
考虑对20个整数的随机输入进行排序，各排序功能基本上都可以成为独立调用的模块，因此可以先写出排序算法，然后用主函数调用。
D．查找及排序算法集成部分
此部分需要学生自行设计，本指导书不给出具体算法。
第二部分：
实验过程记录
实验原始记录（包括实验数据记录，实验现象记录，实验过程发现的问题等）
1．概要设计（说明本程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次或调用关系）
1.1抽象数据类型：
队列：
ADTQueue{
数据对象：
D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}
数据关系：
R1＝{|ai-1,ai∈D,i=2,...,n}
基本操作：
voidinit_Q（Queue&Q）;
操作结果：
构造空队列Q
intQ_empty（QueueQ）;
初始条件：
队列Q存在
操作结果：
若Q为空队列，则返回TRUE,否则FALSE
intQ_length（QueueQ）;
初始条件：
队列Q存在
操作结果：
返回队列Q的元素个数，即队列长度
intgethead_Q（QueueQ）;
初始条件：
队列Q存在
操作结果：
返回队列Q的队头元素
voiden_Q（Queue&Q,inte）;
初始条件：
队列Q存在
操作结果：
插入元素e为Q的新的队尾元素。
voidde_Q（Queue&Q,int&e）;
初始条件：
队列Q存在
操作结果：
删除Q的队头元素。
}ADTQueue
线性表：
ADTList
{
数据对象：
D={ai|1<=i<=n,n>=o,ai属于elementtype类型}
数据关系：
R={|ai,ai+1属于D,i=1,...,n-1}
基本运算：
InitList（&l）
DestroyList（&l）;
......
}
图：
ADTGraph
{
数据对象：
D={ai|1<=i<=n,n>=0,ai属于ELEMTYPE类型}
类型标识符
数据关系：
R={|ai,aj属于D,1<=i<=n,1<=j<=n,其中每个元素可以有零个或多个直接前驱，可以有多个直接后继}
基本运算：
InitGraph（&g）
ClearGraph（&g）
DFS（g）
BFS（g）
.
.
.
}
1.2小问题：
A.随机数的产生：
srand（）函数用于设置随机数种，rand（）用于产生一个随机数。
B.数据的储存：
由于100000个int型数的数组，所以我采用了malloc（）函数来动态分配一数组存储它。
对于一些特别大的数据可以用文件存储，在采用外排序的方式排序。
C.屏幕上无法显示100000条数据，故将数据存储在两个文本文件中。
一个是没排好序的，另一个是排好序后的数据。
1.3主要数据结构设计：
归并排序：
typedefintKeyType;
typedefintDataType;
typedefstruct
{KeyTypekey;/*排序码字段*/
/*DataTypeinfo;记录的其它字段*/}RecordNode;
typedefstruct
{intn;/*n为文件中的记录个数，nRecordNoderecord[MAXNUM];}SortObject;
基数排序:
typedefintKeyType;
typedefintDataType;
typedefstructNodeRadixNode;
structNode
{KeyTypekey[D];
/*DataTypeinfo;*/
RadixNode*next;
};
typedefRadixNode*RadixList;
typedefstructQueueNode
{RadixNode*f;/*队列的头指针*/
RadixNode*e;/*队列的尾指针*/
}Queue;
Hash排序：
typedefstructhnode
{intdata;
structhnode*next;
}HNODE;
typedefstructpoint
{structhnode*pt;
}POINT;
1.4主程序流程：
主程序main（）
输入随机数种子
产生随机数，并存在nonqueue.txt文件中
选择排序方法
7.哈希
6.基数
5.归并
4.快速
3.堆
2.希尔
1.折半
选择排序方法，并存在queue.txt文件中
退出程序
主函数在main.cpp中，排序算法的在各自的头文件中。
选择排序方法后，调用选择的排序方法。
1．5各函数调用关系：
rand（）
BinsertSort（）
ShellInsert（）
fopen（）
srand（）
ShellSort（）
main（）
RadixSort（）
HeapSort（）
mergeSort（）
QuickSort（）
fclose（）
Partition（）
2．详细设计（实现程序模块的具体算法）
2.1主函数：
voidmain（）
{
int*p,n,way,dlta[4]={5,3,2,1},L=11;
longi;
FILE*fp,*fp1;
if（!
（fp=fopen（"queue.txt","w+"）））
printf（"打开文件queue.txt失败!
"）;
if（!
（fp1=fopen（"nonqueue.txt","w+"）））
printf（"打开文件nonqueue.txt失败!
"）;
printf（"请输入随机种子:
\n"）;
scanf（"%d",&n）;
p=（int*）malloc（MAX*sizeof（int））;
for（i=1;i{
p[i]=rand（）;
fprintf（fp1,"%-8d",p[i]）;
}
fclose（fp1）;
printf（"\n\t\t******************************************\n"）;
printf（"\t\t|请选择排序方式|\n"）;
printf（"\t\t||\n"）;
printf（"\t\t|1.折半插入排序算法|\n"）;
printf（"\t\t|2.希尔排序算法|\n"）;
printf（"\t\t|3:
堆排序算法|\n"）;
printf（"\t\t|4.快速排序算法|\n"）;
printf（"\t\t|5.归并排序算法|\n"）;
printf（"\t\t|6.基数排序算法|\n"）;
printf（"\t\t|7.哈希排序算法|\n"）;
printf（"\t\t|0.退出程序|\n"）;
printf（"\t\t******************************************\n"）;
printf（"请输入你的选择：
\n"）;
scanf（"%d",&way）;
switch（way）
{
case0:
exit
（1）;
case1:
BinsertSort（p,MAX-1）;break;
case2:
ShellSort（p,MAX-1,dlta,4）;break;
case3:
HeapSort（p,MAX-1）;break;
case4:
QuickSort（p,MAX-1）;break;
case5:
{
vector.n=MAX-1;
for（i=0;ivector.record[i].key=p[i+1];
mergeSort（&vector）;
for（i=0;ifprintf（fp,"%-8d",vector.record[i].key）;
fclose（fp）;
exit
（1）;
}
case6:
{
RadixListhp;
for（i=0;i{
element[i].key[0]=0;
element[i].key[1]=p[i+1]/10000%10;
element[i].key[2]=p[i+1]/1000%10;
element[i].key[3]=p[i+1]/100%10;
element[i].key[4]=p[i+1]/10%10;
element[i].key[5]=p[i+1]%10;
element[i].next=NULL;
}
for（i=0;ielement[i].next=&element[i+1];
element[MAX-1].next=NULL;
hp=element;
radixSort（&hp,6,10）;
hp=hp->next;
while（hp）
{
fprintf（fp,"%-8d",hp->key[1]*10000+hp->key[2]*1000+hp->key[3]*100+hp->key[4]*10+hp->key[5]）;
hp=hp->next;
}
fclose（fp）;
exit
（1）;
}
case7:
HashSort（p,MAX-1,MAX-1）;break;
}
for（i=1;ifprintf（fp,"%-8d",p[i]）;
fclose（fp）;
}
2.2各排序算法：
（1）归并排序：
#defineMAX100001
#defineMAXNUM100001
#defineTRUE1
#defineFALSE0
typedefintKeyType;
typedefintDataType;
typedefstruct
{KeyTypekey;/*排序码字段*/
/*DataTypeinfo;记录的其它字段*/}RecordNode;
typedefstruct
{longn;/*n为文件中的记录个数，nRecordNoderecord[MAXNUM];}SortObject;
voidmerge（RecordNoder[],RecordNoder1[],longlow,longm,longhigh）
{longi=low,j=m+1,k=low;
while（i<=m&&j<=high）/*反复复制两个段的第一个记录中较小的*/
if（r[i].key<=r[j].key）r1[k++]=r[i++];
elser1[k++]=r[j++];
while（i<=m）r1[k++]=r[i++];/*复制第一个段的剩余记录*/
while（j<=high）r1[k++]=r[j++];/*复制第二个段的剩余记录*/
}
/*对r做一趟归并，结果放到r1中*/
voidmergePass（RecordNoder[],RecordNoder1[],longn,longlength）
{longi=0,j;/*length为本趟归并的有序子段的长度*/
while（i+2*length-1{merge（r,r1,i,i+length-1,i+2*length-1）;/*归并长length的两个子段*/
i+=2*length;}
if（i+length-1merge（r,r1,i,i+length-1,n-1）;
elsefor（j=i;j}
voidmergeSort（SortObject*pvector）
{RecordNoderecord[MAXNUM];
longlength=1;
while（lengthn）/*一趟归并，结果存放在数组record中*/
{mergePass（pvector->record,record,pvector->n,length）;
length*=2;
/*一趟归并，结果存回*/
mergePass（record,pvector->record,pvector->n,length）;
length*=2;}
}
SortObjectvector;
（2）折半插入排序：
voidBinsertSort（intD[],longL）
{longi,j,l,r,m;
for（i=2;i<=L;i++）
{D[0]=D[i];
l=1;
r=i-1;
while（l<=r）{m=（l+r）/2;
if（D[0]elsel=m+1;}
for（j=i-1;j>=r+1;j--）D[j+1]=D[j];
D[r+1]=D[0];}
}
（3）Shell排序：
voidShellInsert（intD[],longL,longdk）
{longi,j;
for（i=dk+1;i<=L;i+=dk）
if（D[i]{D[0]=D[i];
for（j=i-dk;j>0&&D[0]D[j+dk]=D[0];}
}
voidShellSort（intD[],longL,intdlta[],longt）
{longk;
for（k=0;k}
（4）堆排序算法：
voidHeapAdjust（intD[],longs,longm）
{longj;
D[0]=D[s];
for（j=2*s;j<=m;j*=2）
{if（jif（D[0]>=D[j]）break;/*已经符合堆定义，无须浪费时间*/
D[s]=D[j];
s=j;}/*交换，并使s指向新堆*/
D[s]=D[0];/*找到合适的地点就将原堆顶元装进去*/
}
voidHeapSort（intD[],longL）
{longi;
for（i=L/2;i>0;i--）HeapAdjust（D,i,L）;/*将原始序列调整为堆*/
for（i=L;i>1;i--）{D[0]=D[1];
D[1]=D[i];
D[i]=D[0];
HeapAdjust（D,1,i-1）;}
}
（5）快速排序算法：
intPartition（intD[],longl,longr）
{D[0]=D[l];
while（lD[l]=D[r];
while（l=D[l]）l++;
D[r]=D[l];}
D[r]=D[0];
returnr;
}
voidQsort（intD[],longl,longr）
{longp;
if（lQsort（D,l,p-1）;
Qsort（D,p+1,r）;}
}
voidQuickSort（intD[],longL）
{Qsort（D,1,L）;
}
（6）基数排序：
typedefintKeyType;
typedefintDataType;
typedefstructNodeRadixNode;
structNode
{
KeyTypekey[6];/*DataTypeinfo;*/
RadixNode*next;
};
typedefRadixNode*RadixList;
typedefstructQueueNode
{
RadixNode*f;/*队列的头指针*/
RadixNode*e;/*队列的尾指针*/
}Queue;
Queuequeue[10];
voidradixSort（RadixList*plist,intd,intr）
{
inti,j,k;
RadixNode*p,*head=（*plist）->next;
for（j=d-1;j>=0;j--）/*进行d次分配和收集*/
{
p=head;
for（i=0;i{
queue[i].f=NULL;
qu
升级会员 