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

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

2、验报告template <classT> 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);elsedo do i+; while (Ai < Aleft);do j-; while (Aj > A left);if (i < j) Swap(Ai, Aj); while (i < j);Swap(Aleft, Aj);Q

3、Sort(A, left, j - 1);QSort(A, j + 1, right);随机数发生器const int N = 1000;template<class T>void randomizer。* 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 Adouble time;clock_t start, end;cout <&l

4、t; "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函数中各内排序算法调用函数计算时间的语句段简单选择排序时间计算cout << "nSelectS

5、ort:" << endl;Showtime (SelectSort, a);直接插入排序时间计算cout << "nInsertSort:" << endl;Showtime (InsertSort, a);冒泡排序时间计算cout << "nBubbleSort:" << endl;Showtime (BubbleSort, a);快速排序时间计算cout << "nQuickSort:" << endl;Showtime (QuickS

6、ort, a);两路合并排序时间计算cout << "nMergeSort:" << endl;Showtime (MergeSort, a);测试结果如图:HB C:WI N DOW5system 3 2c md. exe X以下所有排序算法所用时间均是排序"0。次一个长度力10Q0的随机数组的总时间,SelectSort：Total time-consuming： L 865InsertSort：Total time-consuming： 04 944BubbleSort:Total time-consuming： 10. 0039ui

7、ckSort:Total time-consuming: 04 233MergeSort:Total time-consiuning ： 0* 6S8请按任意撞继续. . 鲍 C:Wl N DOWSXsy5tem32c md. &xe C X结果表明：速度：改进的快速排序 两路合并排序 直接插入排序 简单选择排序 冒泡排序。四、实验小结（包括问题和解决方法、心得体会、意见与建议等）（一）实验中遇到的主要问题及解决方法问题：InsertSort函数模版已被定义的错误。解决方法：百度错误类型得知，应该是在main.cpp文件中调用头文件QuickSort.h 与InsertSort.h ,而 QuickSort.h 中已经包含了 InserSort.h 文件。问题：快速排序的时间反而比冒泡排序的时间长。解决方法：手工运算代码中的两个排序计算语句段，发现每次调用排序算法函数后没有将随机 数组重