综合排序文档格式.docx
《综合排序文档格式.docx》由会员分享，可在线阅读，更多相关《综合排序文档格式.docx（21页珍藏版）》请在冰点文库上搜索。
构思及收集资料2 图书馆
编程设计与调试5 实验室
撰写论文3 图书馆、实验室
学生签名：
09年12月21日
课程设计（论文）评审意见
（1）完成原理分析（20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（2）设计分析 （20分）：
（3）完成调试 （20分）：
（4）翻译能力 （20分）：
（5）回答问题 （20分）：
（6）格式规范性及考勤是否降等级：
是（ ）、否（ ）
评阅人：
职称：
讲师
09年12月28日
目 录
一、问题描述4
二、内容简介4
2.1基本要求：
4
2.2.算法思想：
2.3.模块划分：
2.4.数据结构：
5
2.5.源程序：
2.6.测试情况：
15
三、小结17
四、参考文献18
一、问题描述
1.如何定义数据类型，并编写书上没有的冒号排序。
2.如何编写时间算法函数计算一个排序所用的时间。
3.如何运用循环实现所有排序算法时间和空间复杂度的比较。
二、内容简介
（1）设计一个的菜单将在实现的功能显示出来，并有选择提示
（2）分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单排序、堆排序算法；
（3）通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较
1.自定义RECNODE结构体；
2.依次定义各种排序的算法；
3.设计一个高精度时间函数，分别测试各种排序的时间消耗；
4.在主函数中，用开关语句swtich（）{case值1;
break;
…case值n;
Default语句序列:
n+1;
}调用各种排序算法，各种排序的时间消耗函数，从而在屏幕上输出供选择的菜单，各种排序时间和空间复杂度的比较。
1.输入初始数据函数：
intMakeList（RECNODE*r）
2.输出未排序前的数据函数：
voidUndealoutList（RECNODE*r,intn）
3.处理后的序列函数：
voidDealoutList（RECNODE*r,intn）
4.这种排序的算法：
voidInsertSort（RECNODE*r,intn）//直接插入排序
voidBiInsertionSort（RECNODE*r,intn）{//折半插入排序
voidBubleSort（RECNODE*r,intn）//冒泡排序
intPartition（RECNODE*r,int*low,int*high）//一趟快速排序
voidQuickSort（RECNODE*r,intstart,intend）//快速排序
voidSeleSort（RECNODE*r,intn）//直接选择排序
voidShellSort（RECNODE*r,intn）//希尔排序
voidSift（RECNODE*r,inti,intm）
voidHeapSort（RECNODE*r,intn）//堆排序
5.排序时间测试函数：
doubleTInsertSort（intlen,RECNODE*a,intp）
1.预定义常量和自定义类型：
#defineMAXSIZE100
typedefstruct
{intkey;
}RECNODE;
2.基本函数的算法用以下形式表示：
函数类型函数名（函数参数表）//算法说明｛语句序列}//函数名。
3.定义intb,t,i,j;
//b为记录交换的次数，t为记录排序的趟数,i为排序的数据，j为暂存数据的临时变量。
4.输入初始数据函数中定义intk,j，k为输入数据个数，j为输入的数据。
5.快速排序中定义staticintw=0,int*low，*high。
6.在直接选择排序中定义intz，临时储存i的值。
7.在希尔排序中定义intdk，记录前后位置的增量。
8.在排序时间消耗测试的函数和主函数中定义了intp，为菜单的序号。
9.在主函数中定义intlen，为测试数据的总长度。
#defineMAXSIZE100//一个用作示例的小顺序表的最大长度
#include<
stdio.h>
/*EOF（=^Z或F6）,NULL*/
#include<
string.h>
ctype.h>
malloc.h>
/*malloc（）等*/
limits.h>
/*INT_MAX等*/
stdlib.h>
/*atoi（）*/
io.h>
/*eof（）*/
iostream>
ctime>
windows.h>
cmath>
usingnamespacestd;
typedefintStatus;
/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;
/*Boolean是布尔类型,其值是TRUE或FALSE*/
intb,t;
//b为记录交换的次数，t为记录排序的趟数
{intj,k;
printf（"
请输入初始数据（每个数据以空格隔开，-1结束）：
"
）;
k=0;
scanf（"
%d"
&
j）;
while（j!
=-1）
{k++;
r[k].key=j;
}
returnk;
}//输入要排序的一组数据，并且返回数据的个数，以-1为结束标志
{inti;
未排序前的数据：
for（i=0;
i<
n;
i++）
%d"
r[i+1].key）;
\n"
{inti;
排序后的数据：
交换或比较的次数：
%d\n"
b）;
排序的趟数：
t）;
voidInsertSort（RECNODE*r,intn）//直接插入排序//
{inti,j;
b=0,t=0;
for（i=2;
=n;
{r[0]=r[i];
//r[0]的作用是暂存空间
j=i-1;
while（r[0].key<
r[j].key）//如果目标数比源数小
{r[j+1]=r[j];
//则让大的数从后往前依次往后挪一个位置，然后让小数插入到恰当位置
j--;
b++;
r[j+1]=r[0];
b++;
t++;
}}
voidBiInsertionSort（RECNODE*r,intn）{//对记录序列R[1..n]作折半插入排序
intlow,high,i,j,m;
for（i=2;
i<
++i）{
r[0]=r[i];
//将R[i]暂存到R[0]/
low=1;
high=i-1;
while（low<
=high）{//在R[low..high]中折半查找插入的位置
m=（low+high）/2;
//折半
if（r[0].key<
r[m].key）
high=m-1;
//插入点在低半区
elselow=m+1;
//插入点在高半区}
for（j=i-1;
j>
=high+1;
--j）
r[j+1]=r[j];
//记录后移
r[high+1]=r[0];
//插入
t++;
b++}}//BInsertSort
RECNODEtemp;
//暂寸空间
for（i=1;
{for（j=n-1;
j>
=i;
j--）//目标数是从第一个数开始，被比较数从最后一个开始
if（r[j+1].key<
r[j].key）//如果目标数比其下一个数要大
{//则两数交换，下一趟比较则还是用原目标数与其下一个书比较
temp=r[j+1];
r[j+1]=r[j];
r[j]=temp;
elseb++;
//否则不用交换，继续和下一个数比较
voidBubleSort（doublea[]）//时间数组的冒泡排序
{inti,j;
doubletemp;
7;
{for（j=5;
j--）
if（a[j+1]<
a[j]）
{temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
b++;
}}
intPartition（RECNODE*r,int*low,int*high）//一躺快速排序//
/*找一个记录，以它的关键字作为"
枢轴"
，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
*/
staticintw=0;
i=*low;
//i指向第一个数
j=*high;
temp=r[i];
//暂存单元，存着目标数
do{//当目标数小于等于要比较的数，并且目标数在左边
while（（r[j].key>
=temp.key）&
&
（i<
j））
{j--;
//则不用换，只要让指向要比较的数的位置左移一位
w++;
if（i<
j）//若遇到一个在目标数右边的小数
{r[i]=r[j];
//则将小数赋给目标数原来所在的位置
i++;
//要比较的数的位置右移一位
while（（r[i].key<
j））
//同理比较，只是现在要比较的数在目标数的右边
{i++;
j）
{r[j]=r[i];
j--;
}while（i!
=j）;
r[i]=temp;
b=w;
//b为记录交换的次数
returni;
voidQuickSort（RECNODE*r,intstart,intend）//快速排序
staticintq=0;
if（start<
end）
{i=Partition（r,&
start,&
end）;
q++;
QuickSort（r,start,i-1）;
//对低子表递归排序，i为中间位置
QuickSort（r,i+1,end）;
//对高子表递归排序}
t=q;
//t为记录排序的趟数}
voidSeleSort（RECNODE*r,intn）//直接选择排序//
//每次都是将无序序列中的最小的数找到，然后依次放到有序序列的最后
{inti,j,z;
{z=i;
for（j=i+1;
j<
j++）//从第i个后的序列中选出最小的一个数
if（r[j].key<
r[z].key）
{z=j;
if（z!
=i）
{temp=r[i];
r[i]=r[z];
r[z]=temp;
voidShellSort（RECNODE*r,intn）//希尔排序//
{inti,j,dk;
//dk记录前后位置的增量
dk=n/2;
while（dk>
0）//一趟增量为dk的插入排序
{for（i=dk+1;
++i）
if（r[i].key<
r[i-dk].key）//将r[i]插入有序增量子表
{r[0]=r[i];
//r[0]为暂存单元
for（j=i-dk;
0&
r[0].key<
r[j].key;
j-=dk）
{r[j+dk]=r[j];
//记录后移，查找插入位置}
r[j+dk]=r[0];
dk=dk/2;
//增量改为原来的一半
voidSift（RECNODE*r,inti,intm）
{intj;
staticintx=0;
j=2*i;
while（j<
=m）//沿key较大的孩子结点向下筛选
{if（j<
m&
（r[j].key<
r[j+1].key））//j为key较大的记录的下标
{j++;
x++;
if（temp.key<
r[j].key）
{r[i]=r[j];
i=j;
elsex++;
break;
b=x;
}
voidHeapSort（RECNODE*r,intn）//堆排序
{RECNODEtemp;
inti;
t=0;
for（i=n/2;
i>
=1;
--i）
Sift（r,i,n）;
//建大顶堆
for（i=n;
=2;
--i）//将堆顶记录和当前未经排序子序列
//H.r[1..i]中最后一个记录相互交换
{temp=r[1];
r[1]=r[i];
Sift（r,1,i-1）;
//对H.r[1]进行筛选
doubleTInsertSort（intlen,RECNODE*a,intp）{
if（p!
=8）{len=MakeList（a）;
UndealoutList（a,len）;
}
//若为时间效率全比较，则不用把比较的具体过程输出，只需输出排序时间
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&
m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&
m_liPerfStart）;
InsertSort（a,len）;
if（p!
=8）{DealoutList（a,len）;
}
LARGE_INTEGERliPerfNow={0};
liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
cout<
<
"
直接插入排序时间消耗：
time<
MS"
;
return（time）;
}//直接插入排序时间测试
doubleTBiInsertionSort（intlen,RECNODE*a,intp）{
折半插入排序时间消耗：
}//折半插入排序时间测试
doubleTBubleSort（intlen,RECNODE*a,intp）{if（p!
=8）
{len=MakeList（a）;
BubleSort（a,len）;
冒泡排序序时间消耗：
}//冒泡排序时间测试
doubleTQuickSort（intlen,RECNODE*a,intp）{
=8）{len=MakeList（a）;
QuickSort（a,1,len）;
快速排序时间消耗：
}//快速排序时间测试
doubleTSeleSort（intlen,RECNODE*a,intp）{
SeleSort（a,len）;
=8）{DealoutList（a,len）;
LARGE_I
升级会员 