实验报告4.docx

实验报告4.docx

《实验报告4.docx》由会员分享，可在线阅读，更多相关《实验报告4.docx（14页珍藏版）》请在冰点文库上搜索。

实验报告4

实验报告4

01540802班

姜沛杰

学号：

20080697

本次上机实验我们编写了关于几个排序问题的程序。

实验目的：

练习常用的几种排序方法，同时锻炼标准化编程的能力；

所用知识：

插入排序，希尔排序，堆排序，归并排序，快速排序以及其他必要的编程知识；

程序设计思路为：

分别应用插入排序、希尔排序、堆排序、归并排序、快速排序各种排序方法，对由随机产生的数组进行排序，输出排序结果和排序需要的时间，比较各种排序的效率。

程序源代码为：

#include

#include

#include

#defineTotal10

voidRand（inta[]）

{

inti;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

}

voidPrint（inta[],intN）

{

inti;

for（i=0;i

printf（"%d",a[i]）;

printf（"\n"）;

}

//insertionsortO（N2）

voidInsertionSort（inta[],intN）/*插入排序*/

{

inti,j,Tmp;

for（i=0;i

{

Tmp=a[i];

for（j=i;j>0&&a[j-1]>Tmp;j--）

a[j]=a[j-1];

a[j]=Tmp;

}

}

//ShellsortO（N2）

voidShellSort（inta[],intN）/*希尔排序*/

{

inti,j,Increment,Tmp;

for（Increment=N/2;Increment>0;Increment/=2）

for（i=Increment;i

{

Tmp=a[i];

for（j=i;j>=Increment;j-=Increment）

if（Tmp

a[j]=a[j-Increment];

else

break;

a[j]=Tmp;

}

}

//heapsortO（NlogN）

#defineLeftChild（i）（2*（i）+1）

voidSwap（int*a,int*b）

{

int*tmp;

tmp=（int*）malloc（sizeof（int））;

*tmp=*a;

*a=*b;

*b=*tmp;

}

voidPercDown（inta[],inti,intN）

{

intChild;

intTmp;

for（Tmp=a[i];LeftChild（i）

{

Child=LeftChild（i）;

if（Child!

=N-1&&a[Child+1]>a[Child]）

Child++;

if（Tmp

a[i]=a[Child];

else

break;

}

a[i]=Tmp;

}

voidHeapSort（inta[],intN）/*堆排序*/

{

inti;

for（i=N/2;i>=0;i--）

PercDown（a,i,N）;

for（i=N-1;i>0;i--）

{

Swap（&a[0],&a[i]）;

PercDown（a,0,i）;

}

}

//mergesortO（NlogN）

voidMerge（inta[],intTmpArray[],intLpos,intRpos,intRightEnd）/*归并排序*/

{

inti,LeftEnd,Num,TmpPos;

LeftEnd=Rpos-1;

TmpPos=Lpos;

Num=RightEnd-Lpos+1;

while（Lpos<=LeftEnd&&Rpos<=RightEnd）

if（a[Lpos]<=a[Rpos]）

TmpArray[TmpPos++]=a[Lpos++];

else

TmpArray[TmpPos++]=a[Rpos++];

while（Lpos<=LeftEnd）

TmpArray[TmpPos++]=a[Lpos++];

while（Rpos<=RightEnd）

TmpArray[TmpPos++]=a[Rpos++];

for（i=0;i

{

a[RightEnd]=TmpArray[RightEnd];

}

}

voidMsort（inta[],intTmpArray[],intLeft,intRight）

{

intCenter;

if（Left

{

Center=（Left+Right）/2;

Msort（a,TmpArray,Left,Center）;

Msort（a,TmpArray,Center+1,Right）;

Merge（a,TmpArray,Left,Center+1,Right）;

}

}

voidMergeSort（inta[],intN）

{

int*TmpArray;

TmpArray=（int*）malloc（Total*sizeof（int））;

if（TmpArray!

=NULL）

{

Msort（a,TmpArray,0,N-1）;

//free（TmpArray）;

}

else

{printf（"error\n"）;

exit（0）;

}

}

//Quicksort

#defineCutoff3

intMedian3（inta[],intLeft,intRight）

{

intCenter=（Left+Right）/2;

if（a[Left]>a[Center]）

Swap（&a[Left],&a[Center]）;

if（a[Left]>a[Right]）

Swap（&a[Left],&a[Right]）;

if（a[Center]>a[Right]）

Swap（&a[Center],&a[Right]）;

Swap（&a[Center],&a[Right-1]）;

returna[Right-1];

}

voidQuickSort（inta[],intLeft,intRight）/*快速排序*/

{

inti,j;

intPivot;

if（Left+Cutoff<=Right）

{

Pivot=Median3（a,Left,Right）;

i=Left;

j=Right-1;

for（;;）

{

while（a[++i]

while（a[--j]>Pivot）;

if（i

Swap（&a[i],&a[j]）;

else

break;

}

Swap（&a[i],&a[Right-1]）;

QuickSort（a,Left,i-1）;

QuickSort（a,i,Right）;

}

else

InsertionSort（a+Left,Right-Left+1）;

}

//main

intmain（）

{

inti;

inta[Total];

longstart,end1,end2,end3,end4,end5;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

printf（"Data:

\n"）;

Print（a,Total）;

start=clock（）;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

InsertionSort（a,Total）;

printf（"InsertionSort:

\n"）;

Print（a,Total）;

end1=clock（）;

printf（"TheRunningTimeofInsertionSort:

%ld\n",end1-start）;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

ShellSort（a,Total）;

printf（"ShellSort:

\n"）;

Print（a,Total）;

end2=clock（）;

printf（"TheRunningTimeofShellSort:

%ld\n",end2-end1）;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

HeapSort（a,Total）;

printf（"HeapSort:

\n"）;

Print（a,Total）;

end3=clock（）;

printf（"TheRunningTimeofHeapSort:

%ld\n",end3-end2）;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

MergeSort（a,Total）;

printf（"MergeSort:

\n"）;

Print（a,Total）;

end4=clock（）;

printf（"TheRunningTimeofMergeSort:

%ld\n",end4-end3）;

srand

（1）;

for（i=0;i

a[i]=rand（）%（Total*10）;

QuickSort（a,0,Total-1）;

printf（"QuickSort:

\n"）;

Print（a,Total）;

end5=clock（）;

printf（"TheRunningTimeofQuickSort:

%ld\n",end5-end4）;

return0;

}

（三）程序运行结果：

（1）将Total定义为10，输出结果为：

Data:

4167340692478586264

InsertionSort:

0243441586264676978

TheRunningTimeofInsertionSort:

0

ShellSort:

0243441586264676978

TheRunningTimeofShellSort:

5

HeapSort:

0243441586264676978

TheRunningTimeofHeapSort:

0

MergeSort:

0243441586264676978

TheRunningTimeofMergeSort:

1

QuickSort:

0243441586264676978

TheRunningTimeofQuickSort:

0

Pressanykeytocontinue

（2）将Total定义为100，输出结果为：

Data:

41467334500169724478358962464705145281827961491995942827436

391604902153292382421716718895447726771538869912667299358947

038113223336736641417112538685476446627573785972374152977831

63519084228810640942264648446805890729370350610139354862962

38495475684096637693130894443962632353753811882929541

InsertionSort:

635353740418284101106118141145153169190253264281288292299

308316322323333334350358370376382391393421436439446447464467

478491500529537538538541547548604623626629644648662664667673

703705711716718723724726729741756757771778805811827827840842

859868869890894895902912929931942942944954961962966995

TheRunningTimeofInsertionSort:

5

ShellSort:

635353740418284101106118141145153169190253264281288292299

308316322323333334350358370376382391393421436439446447464467

478491500529537538538541547548604623626629644648662664667673

703705711716718723724726729741756757771778805811827827840842

859868869890894895902912929931942942944954961962966995

TheRunningTimeofShellSort:

6

HeapSort:

635353740418284101106118141145153169190253264281288292299

308316322323333334350358370376382391393421436439446447464467

478491500529537538538541547548604623626629644648662664667673

703705711716718723724726729741756757771778805811827827840842

859868869890894895902912929931942942944954961962966995

TheRunningTimeofHeapSort:

10

MergeSort:

635353740418284101106118141145153169190253264281288292299

308316322323333334350358370376382391393421436439446447464467

478491500529537538538541547548604623626629644648662664667673

703705711716718723724726729741756757771778805811827827840842

859868869890894895902912929931942942944954961962966995

TheRunningTimeofMergeSort:

18

QuickSort:

635353740418284101106118141145153169190253264281288292299

308316322323333334350358370376382391393421436439446447464467

478491500529537538538541547548604623626629644648662664667673

703705711716718723724726729741756757771778805811827827840842

859868869890894895902912929931942942944954961962966995

TheRunningTimeofQuickSort:

15

Pressanykeytocontinue

（3）将Total定义为10000，输出结果为（为了输出方便，不输出原始数据和排序后的结果）：

Data:

InsertionSort:

TheRunningTimeofInsertionSort:

239

ShellSort:

TheRunningTimeofShellSort:

173

HeapSort:

TheRunningTimeofHeapSort:

9

MergeSort:

TheRunningTimeofMergeSort:

4

QuickSort:

TheRunningTimeofQuickSort:

21

Pressanykeytocontinue

（4）将Total定义为50000，输出结果为（为了输出方便，不输出原始数据和排序后的结果）：

Data:

InsertionSort:

TheRunningTimeofInsertionSort:

5982

ShellSort:

TheRunningTimeofShellSort:

5201

HeapSort:

TheRunningTimeofHeapSort:

46

MergeSort:

TheRunningTimeofMergeSort:

24

QuickSort:

TheRunningTimeofQuickSort:

114

Pressanykeytocontinue

实验收获：

通过对较多的数据排序可以发现，在需要排序的数据量较少的时候，快速排序、归并排序和堆排序的优势并不明显，但是在需要排序的数据量十分大的时候，快速排序、归并排序和堆排序的效率十分高，远远高于插入排序和希尔排序。

通过此次上机实验，巩固了各种排序方法，同时练习了编写程序的方法。

增强了对各种排序算法的理解，同时加深了对在需要处理的数据量非常大的时候，算法的效率对结果的产生十分的重要。