(完整word版)各种内排序算法的实现及性能比较

1、实验报告实验名称各种内排序算法的实现及性能比较指导教师实验类型设计实验学时2实验时间一、实验目的和要求（ 1） 理解和掌握各种排序算法。（ 2） 学会比较排序方法的性能。二、 实验环境 (实验设备 )硬件：微型计算机软件： Windows 操作系统、 Microsoft Visual Studio 2015三、实验原理及内容QSortQuickSortA,j-1A,0,n-1A,nA,left,rightInsertSortQSort/改进的快速排序template <class T>void QuickSort (T A , int n)QSort(A , 0, n - 1);1

2、实验报告template <class T>void QSort(T A ,int left ,int right )int i, j;if (left < right )i = left ; j = right + 1;if (j-i < 10 )/ 如果子集合小于10个元素时改用直接插入排序InsertSort( A, j-i );else do do i+; while (A i < A left );do j-; while (A j > A left );if (i < j ) Swap(A i, A j) ; while (i < j

3、 ); Swap(A left , A j); QSort(A , left , j - 1); QSort(A , j + 1, right);/随机数发生器const int N = 1000;template<class T>void randomizer(T* a)srand(time(NULL );for (int i = 0; i < N; i+ )ai = rand() % 10000;/各内排序时间计算函数template<class T>void Showtime (void (* Order)(T A , int n),T A )2实验报告do

4、uble time;clock_t start, end;cout << "Total time-consuming:"start = clock ();/ 开始计时for (int i = 0; i < 1000; i+ )Order(A , N );randomizer (A );end = clock() ;/结束计时time = ( double)(end - start) / CLOCKS_PER_SEC ;/ 耗时为两者差值除以clock 中每秒的值cout << time << endl;/main 函数中各内排序算法

5、调用函数计算时间的语句段/ 简单选择排序时间计算cout << "nSelectSort:" << endl;Showtime (SelectSort, a);/ 直接插入排序时间计算cout << "nInsertSort:" << endl;Showtime (InsertSort, a);/ 冒泡排序时间计算cout << "nBubbleSort:"<< endl;Showtime (BubbleSort, a );/ 快速排序时间计算cout <&

6、lt; "nQuickSort:"<< endl;Showtime (QuickSort, a );/ 两路合并排序时间计算cout << "nMergeSort:"<< endl;Showtime (MergeSort, a) ;3实验报告测试结果如图：结果表明：速度：改进的快速排序>两路合并排序>直接插入排序 >简单选择排序>冒泡排序。4实验报告四、实验小结 （包括问题和解决方法、心得体会、意见与建议等）( 一 ) 实验中遇到的主要问题及解决方法问题： InsertSort函数模版已被定义的错误。解决方法：百度错误类型得知，应该是在main.cpp文件中调用头文件QuickSort.h与InsertSort.h，而 QuickSort.h中已经包含了InserSort.h文件。问题：快速排序的时间反而比冒泡排序的时间长。解决方法：手工运算代码中的两个排序计算语句段，发现每次调用排序算法函数后没有将随机数组重新随机生成， 而冒泡排序