实验九 内部排序Word文档下载推荐.docx
- 文档编号:7651442
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:19
- 大小:98.86KB
实验九 内部排序Word文档下载推荐.docx
《实验九 内部排序Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《实验九 内部排序Word文档下载推荐.docx(19页珍藏版)》请在冰点文库上搜索。
StatusCopySqList(SqListL_BAK,SqList*L);
//
StatusOutputSqList(SqListL);
//输出排序之后的数据
intLT(KeyTypee1,KeyTypee2);
//判断数据元素e1是否小余e2
voidSwap(RedType*e1,RedType*e2);
//数据元素e1和e2互换
StatusInsertSort(SqList*L);
//直接排入排序
StatusBInsertSort(SqList*L);
//折半插入排序
StatusShellInsert(SqList*L,intdk);
//一趟希尔排序
StatusShellSort(SqList*L,intdlta[],intt);
//希尔排序
StatusBubbleSort(SqList*L);
//冒泡排序
intPartition(SqList*L,intlow,inthigh);
//一趟快速排序
voidQSort(SqList*L,intlow,inthigh);
//对L中子序列L.r[low..high]进行快速排序
StatusQuickSort(SqList*L);
//对L进行快速排序
StatusSelectSort(SqList*L);
//直接选择排序
StatusHeapAdjust(SqList*H,intS,intm);
//调整L.r[s]的关键字,使L.r[s..m]成大顶堆
StatusHeapSort(SqList*L);
//堆排序
StatusMerge(SqList*L,intlow,intmid,inthigh);
//将两个有序的子序列L.r[low..mid]和L.r[mid..high]归并成有序的序列L.r[low..high]
voidMSort(SqList*L,intlen);
//对L.r[1..n]做一趟归并排序
StatusMergeSort(SqList*L);
//对L.r[1..n]自底向上二路归并排序
voidmain(){//典型部排序的比较
SqListL,L_BAK;
intselect,flag=1,t,dlta[MAXSIZE];
doubleduration;
clock_tstart,finish;
//clock_t用于计时
InitSqList(&
L);
L_BAK);
CreateSqList(&
t=0;
//产生希尔排序的增量序列dlta[0..t]
dlta[0]=L_BAK.length/2;
while(dlta[t]>
1){
dlta[t+1]=dlta[t]/2;
t++;
}
while(flag){
CopySqList(L_BAK,&
printf("
Pleaseselect:
\n"
);
1.InsertSort\n"
2.BInsertSort\n"
3.ShellSort\n"
4.BubbleSort\n"
5.QuickSort\n"
6.SelectSort\n"
7.HeapSort\n"
8.MergeSort\n"
9.Exit\n"
scanf("
%d"
&
select);
switch(select){
case1:
printf("
\nNowisinInsertSort......"
start=clock();
InsertSort(&
finish=clock();
break;
case2:
\nNowisinBInsertSort......"
BInsertSort(&
case3:
\nNowisinShellSort......"
ShellSort(&
L,dlta,t+1);
case4:
\nNowisinBUbbleSort......"
BubbleSort(&
case5:
\nNowisinQuickSort......"
QuickSort(&
case6:
\nNowisinSelectSort......"
SelectSort(&
case7:
\nNowisinHeapSort......"
HeapSort(&
case8:
\nNowisinMergeSort......"
MergeSort(&
default:
flag=0;
printf("
Pressanykeytoexit!
getch();
}
OutputSqList(L);
duration=(double)(finish-start)/CLK_TCK;
//输出算数时间
\nTheSortSpend:
%lfseconds\n"
duration);
}
StatusInitSqList(SqList*L){
L->
r=(RedType*)malloc((MAXSIZE+1)*sizeof(RedType));
//分配存
if(!
L->
r)
exit(OVERFLOW);
length=0;
returnOK;
StatusCreateSqList(SqList*L){
inti;
srand(time(NULL));
printf("
\nPleaseInputtheNumberofUnSortedData:
"
scanf("
length);
for(i=1;
i<
=L->
length;
i++)
L->
r[i].key=rand();
//随机产生整数样本
\n\nTheUnSorteddatais:
%8d"
L->
r[i].key);
StatusCopySqList(SqListL_BAK,SqList*L){
L_BAK.length){
TheSqListisEmpty!
"
returnERROR;
=L_BAK.length;
r[i].key=L_BAK.r[i].key;
length=L_BAK.length;
StatusOutputSqList(SqListL){
\nTheLengthofSqListis:
%d\n"
L.length);
\n\nTheSortedDatais:
=L.length;
L.r[i]);
intLT(KeyTypee1,KeyTypee2){
if(e1<
e2)
return1;
else
return0;
voidSwap(RedType*e1,RedType*e2){
RedTypee;
e=*e1;
*e1=*e2;
*e2=e;
StatusInsertSort(SqList*L){
inti,j;
length){
for(i=2;
if(LT(L->
r[i].key,L->
r[i-1].key)){
L->
r[0]=L->
r[i];
r[i]=L->
r[i-1];
for(j=i-2;
LT(L->
r[0].key,L->
r[j].key);
j--)
L->
r[j+1]=L->
r[j];
r[0];
StatusBInsertSort(SqList*L){
inti,j,mid,low,high;
i++){
low=1;
high=i-1;
while(low<
=high){
mid=(low+high)/2;
if(LT(L->
r[mid].key))
high=mid-1;
else
low=mid+1;
for(j=i-1;
j>
=high+1;
r[high+1]=L->
StatusShellInsert(SqList*L,intdk){
for(i=dk+1;
r[i-dk].key)){
for(j=i-dk;
0&
&
j-=dk)
r[j+dk]=L->
StatusShellSort(SqList*L,intdlta[],intt){
intk;
for(k=0;
k<
t;
k++)
ShellInsert(L,dlta[k]);
StatusBubbleSort(SqList*L){
for(j=1;
j<
length-i;
j++)
if(!
r[j].key,L->
r[j+1].key))
Swap(&
r[j],&
r[j+1]);
intPartition(SqList*L,intlow,inthigh){
intpivotkey;
r[low];
pivotkey=L->
r[low].key;
while(low<
high){
high&
r[high].key>
=pivotkey)
high--;
r[low]=L->
r[high];
r[high].key<
low++;
r[high]=L->
returnlow;
voidQSort(SqList*L,intlow,inthigh){
if(low<
pivotkey=Partition(L,low,high);
QSort(L,low,pivotkey-1);
QSort(L,pivotkey+1,high);
StatusQuickSort(SqList*L){
QSort(L,1,L->
StatusSelectSort(SqList*L){
inti,j,min;
min=i;
for(j=i+1;
r[min].key))
min=j;
if(min!
=i)
Swap(&
r[i],&
r[min]);
StatusHeapAdjust(SqList*H,ints,intm){
intj;
H->
r[0]=H->
r[s];
for(j=2*s;
=m;
j*=2){
if(j<
m&
LT(H->
r[j].key,H->
j++;
if(!
r[0].key,H->
r[j].key))
break;
H->
r[s]=H->
s=j;
StatusHeapSort(SqList*H){
H->
for(i=H->
length/2;
i>
0;
i--)
HeapAdjust(H,i,H->
1;
i--){
Swap(&
r[1],&
r[i]);
HeapAdjust(H,1,i-1);
StatusMerge(SqList*L,intlow,intmid,inthigh){
inti=low,j=mid+1,k=0;
//赋初值
SqListL1;
//L1暂存L.r[low..mid]和L.r[mid+1..high]归并后的结果
L1.r=(RedType*)malloc((high-low+1)*sizeof(RedType));
L1.r)
while(i<
=mid&
=high)//两个子序列非空时,取其小者输出到L1.r[k]上
L1.r[k++]=LT(L->
r[j].key)?
r[i++]:
r[j++];
=mid)//复制第一个子序列的剩余记录到L1
L1.r[k++]=L->
r[i++];
while(j<
=high)//复制第二个子序列的剩余记录到L1
for(k=0,i=low;
=high;
k++,i++)
r[i].key=L1.r[k].key;
//将归并结果复制回L->
r[low..high]
voidMSort(SqList*L,intlen){
i+2*len-1<
i=i+2*len)//归并长度为len的两个相邻的子序列
Merge(L,i,i+len-1,i+2*len-1);
if(i+len-1<
length)//仍有一个子序列,其中后一个长度小于len;
此时,若i<
length且i+len-1>
length时,则剩余一个子序列轮空,无须归并
Merge(L,i,i+len-1,L->
//归并最后两个子序列
StatusMergeSort(SqList*L){
intlen;
for(len=1;
len<
len*=2)//有效长度len>
=n时终止
MSort(L,len);
结果:
1、样本数量为100时:
依次进行8种排序的执行时间:
2、样本数量为1000时:
......
8种排序执行时间依次为:
结果分析:
经多次排序发现,8种排序方法存在一定的执行速度差异,但是并不明显,而且其时间复杂度与随机序列情况有关,不同的序列即使样本数相同采用相同的排序方法执行时间也有不同,而同一序列采用不同的排序方法执行时间也可能不同,针对某一特定序列,只有采用其最适合的一种排序方法才会效率最高,而当样本数量较小时由上述实验可知执行时间均为0。
(2)一趟排序(一趟希尔插入排序、一趟快速排序、一趟归并排序)
目录部分:
1.ShellInsert\n"
2.Partition\n"
3.MSort\n"
选项操作:
case1:
\nNowisinShellInsert......"
start=clock();
ShellInsert(&
L,dlta[0]);
finish=clock();
break;
case2:
\nNowisinPartition......"
Partition(&
L,1,L.length);
case3:
\nNowisinMSort......"
MSort(&
L,1);
default:
getch();
执行结果:
(1)样本数量为20、一趟希尔排序结果:
(2)一趟快速排序:
(3)一趟归并排序:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验九 内部排序 实验 内部 排序
![提示](https://static.bingdoc.com/images/bang_tan.gif)