实验报告4.docx

1、实验报告4实验报告401540802班姜沛杰学号：20080697本次上机实验我们编写了关于几个排序问题的程序。实验目的：练习常用的几种排序方法，同时锻炼标准化编程的能力；所用知识：插入排序，希尔排序，堆排序，归并排序，快速排序以及其他必要的编程知识；程序设计思路为：分别应用插入排序、希尔排序、堆排序、归并排序、快速排序各种排序方法，对由随机产生的数组进行排序，输出排序结果和排序需要的时间，比较各种排序的效率。程序源代码为：#include #include #include #define Total 10void Rand (int a ) int i; srand(1); for(i=0

2、;iTotal;i+) ai=rand()%(Total*10);void Print( int a ,int N) int i; for(i=0;iN;i+) printf( %d,ai); printf(n);/ insertion sort O(N2)void InsertionSort ( int a , int N ) /*插入排序*/ int i, j, Tmp; for( i=0 ; i0 & aj-1 Tmp ; j-) aj=aj-1; aj=Tmp; /Shellsort O(N2)void ShellSort ( int a , int N ) /*希尔排序*/ int

3、i,j,Increment,Tmp; for( Increment=N/2 ; Increment0 ; Increment/=2 ) for ( i=Increment ;i=Increment ; j-=Increment ) if (Tmp aj-Increment) aj=aj-Increment; else break; aj=Tmp; / heapsort O (N log N)#define LeftChild(i) ( 2*(i)+1)void Swap (int *a ,int *b) int *tmp; tmp = (int *) malloc ( sizeof(int)

4、); *tmp=*a; *a=*b; *b=*tmp;void PercDown ( int a ,int i, int N) int Child; int Tmp; for(Tmp = ai ; LeftChild(i) aChild ) Child+; if (Tmp=0 ; i- ) PercDown (a,i,N); for( i=N-1 ; i0 ; i- ) Swap(&a0,&ai); PercDown (a,0,i); /mergesort O (N log N)void Merge ( int a ,int TmpArray ,int Lpos , int Rpos ,int

5、 RightEnd) /*归并排序*/ int i , LeftEnd , Num , TmpPos; LeftEnd = Rpos - 1; TmpPos = Lpos ; Num = RightEnd - Lpos +1; while ( Lpos = LeftEnd & Rpos = RightEnd ) if(aLpos = aRpos ) TmpArray TmpPos+ = aLpos+; else TmpArray TmpPos+ = aRpos+; while(Lpos=LeftEnd) TmpArray TmpPos+ = aLpos+; while(Rpos=RightEn

6、d) TmpArray TmpPos+ = aRpos+; for( i=0 ; iNum ; i+ , RightEnd- ) a RightEnd = TmpArray RightEnd ; void Msort (int a , int TmpArray , int Left ,int Right ) int Center; if( 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

7、Center , &a Right ); Swap( &aCenter , &aRight-1 ); return a Right-1 ;void QuickSort ( int a , int Left , int Right ) /*快速排序*/ int i,j; int Pivot; if( Left+Cutoff = Right ) Pivot = Median3( a , Left , Right ); i = Left ; j = Right -1; for( ; ; ) while ( a+i Pivot ); if(ij) Swap ( &ai ,&aj ); else bre

8、ak; Swap ( &ai , &aRight-1 ); QuickSort ( a , Left , i-1 ); QuickSort ( a , i , Right ); else InsertionSort ( a+Left , Right-Left+1 );/mainint main () int i; int aTotal; long start,end1,end2,end3,end4,end5; srand(1); for(i=0;iTotal;i+) ai=rand()%(Total*10); printf(Data:n); Print(a,Total); start = cl

9、ock(); srand(1); for(i=0;iTotal;i+) ai=rand()%(Total*10); InsertionSort ( a , Total ); printf(InsertionSort:n); Print(a,Total); end1 = clock(); printf(The Running Time of InsertionSort :%ldn,end1-start); srand(1); for(i=0;iTotal;i+) ai=rand()%(Total*10); ShellSort ( a , Total ); printf(ShellSort:n);

10、 Print(a,Total); end2 = clock(); printf(The Running Time of ShellSort :%ldn,end2-end1); srand(1); for(i=0;iTotal;i+) ai=rand()%(Total*10); HeapSort ( a , Total ); printf(HeapSort:n); Print(a,Total); end3 = clock(); printf(The Running Time of HeapSort :%ldn,end3-end2); srand(1); for(i=0;iTotal;i+) ai

11、=rand()%(Total*10); MergeSort ( a , Total ); printf(MergeSort:n); Print(a,Total); end4 = clock(); printf(The Running Time of MergeSort :%ldn,end4-end3); srand(1); for(i=0;iTotal;i+) ai=rand()%(Total*10); QuickSort ( a , 0,Total-1 ); printf(QuickSort:n); Print(a,Total); end5 = clock(); printf(The Run

12、ning Time of QuickSort :%ldn,end5-end4); return 0;（三）程序运行结果：（1） 将Total定义为10，输出结果为：Data: 41 67 34 0 69 24 78 58 62 64InsertionSort: 0 24 34 41 58 62 64 67 69 78The Running Time of InsertionSort :0ShellSort: 0 24 34 41 58 62 64 67 69 78The Running Time of ShellSort :5HeapSort: 0 24 34 41 58 62 64 67 6

13、9 78The Running Time of HeapSort :0MergeSort: 0 24 34 41 58 62 64 67 69 78The Running Time of MergeSort :1QuickSort: 0 24 34 41 58 62 64 67 69 78The Running Time of QuickSort :0Press any key to continue（2） 将Total定义为100，输出结果为：Data: 41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 94

14、2 827 436391 604 902 153 292 382 421 716 718 895 447 726 771 538 869 912 667 299 35 894 703 811 322 333 673 664 141 711 253 868 547 644 662 757 37 859 723 741 529 778 316 35 190 842 288 106 40 942 264 648 446 805 890 729 370 350 6 101 393 548 629 623 84 954 756 840 966 376 931 308 944 439 626 323 53

15、7 538 118 82 929 541InsertionSort: 6 35 35 37 40 41 82 84 101 106 118 141 145 153 169 190 253 264 281 288 292 299308 316 322 323 333 334 350 358 370 376 382 391 393 421 436 439 446 447 464 467478 491 500 529 537 538 538 541 547 548 604 623 626 629 644 648 662 664 667 673703 705 711 716 718 723 724 7

16、26 729 741 756 757 771 778 805 811 827 827 840 842859 868 869 890 894 895 902 912 929 931 942 942 944 954 961 962 966 995The Running Time of InsertionSort :5ShellSort: 6 35 35 37 40 41 82 84 101 106 118 141 145 153 169 190 253 264 281 288 292 299308 316 322 323 333 334 350 358 370 376 382 391 393 42

17、1 436 439 446 447 464 467478 491 500 529 537 538 538 541 547 548 604 623 626 629 644 648 662 664 667 673703 705 711 716 718 723 724 726 729 741 756 757 771 778 805 811 827 827 840 842859 868 869 890 894 895 902 912 929 931 942 942 944 954 961 962 966 995The Running Time of ShellSort :6HeapSort: 6 35

18、 35 37 40 41 82 84 101 106 118 141 145 153 169 190 253 264 281 288 292 299308 316 322 323 333 334 350 358 370 376 382 391 393 421 436 439 446 447 464 467478 491 500 529 537 538 538 541 547 548 604 623 626 629 644 648 662 664 667 673703 705 711 716 718 723 724 726 729 741 756 757 771 778 805 811 827

19、827 840 842859 868 869 890 894 895 902 912 929 931 942 942 944 954 961 962 966 995The Running Time of HeapSort :10MergeSort: 6 35 35 37 40 41 82 84 101 106 118 141 145 153 169 190 253 264 281 288 292 299308 316 322 323 333 334 350 358 370 376 382 391 393 421 436 439 446 447 464 467478 491 500 529 53

20、7 538 538 541 547 548 604 623 626 629 644 648 662 664 667 673703 705 711 716 718 723 724 726 729 741 756 757 771 778 805 811 827 827 840 842859 868 869 890 894 895 902 912 929 931 942 942 944 954 961 962 966 995The Running Time of MergeSort :18QuickSort: 6 35 35 37 40 41 82 84 101 106 118 141 145 15

21、3 169 190 253 264 281 288 292 299308 316 322 323 333 334 350 358 370 376 382 391 393 421 436 439 446 447 464 467478 491 500 529 537 538 538 541 547 548 604 623 626 629 644 648 662 664 667 673703 705 711 716 718 723 724 726 729 741 756 757 771 778 805 811 827 827 840 842859 868 869 890 894 895 902 91

22、2 929 931 942 942 944 954 961 962 966 995The Running Time of QuickSort :15Press any key to continue（3） 将Total定义为10000，输出结果为（为了输出方便，不输出原始数据和排序后的结果）：Data:InsertionSort:The Running Time of InsertionSort :239ShellSort:The Running Time of ShellSort :173HeapSort:The Running Time of HeapSort :9MergeSort:Th

23、e Running Time of MergeSort :4QuickSort:The Running Time of QuickSort :21Press any key to continue（4） 将Total定义为50000，输出结果为（为了输出方便，不输出原始数据和排序后的结果）：Data:InsertionSort:The Running Time of InsertionSort :5982ShellSort:The Running Time of ShellSort :5201HeapSort:The Running Time of HeapSort :46MergeSort:The Running Time of MergeSort :24QuickSort:The Running Time of QuickSort :114Press any key to continue实验收获：通过对较多的数据排序可以发现，在需要排序的数据量较少的时候，快速排序、归并排序和堆排序的优势并不明显，但是在需要排序的数据量十分大的时候，快速排序、归并排序和堆排序的效率十分高，远远高于插入排序和希尔排序。通过此次上机实验，巩固了各种排序方法，同时练习了编写程序的方法。增强了对各种排序算法的理解，同时加深了对在需要处理的数据量非常大的时候，算法的效率对结果的产生十分的重要。