算法排序实验报告包括对五种排序算法的算法实现时间的比较.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

randoll814814-1770228-4744300845144537880.doc.pdf-第1页.png

第1页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第2页.png

第2页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第3页.png

第3页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第4页.png

第4页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第5页.png

第5页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第6页.png

第6页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第7页.png

第7页 / 共9页

randoll814814-1770228-4744300845144537880.doc.pdf-第8页.png

第8页 / 共9页

实验目的: 比较各排序算法

实验环境: Vista + VS 2005 .net 使用语言: C++

设计的基本思路:

程序清单:

实验结果:

1.当Length为 1000时:

2.当Length为 10000时:

3.当Length为 100000时:

实验目的: 比较各排序算法实验环境: Vista + VS 2005 .net 使用语言: C++ 设计的基本思路: 首先将各个排序算法写成函数，函数所需要接收的参数是数组的长度 Length，将 Length 定义在 main 函数外边并申明为 const。利用系统时间 time(0)作为随机数的种子，保证随机数的唯一性，生成的随机数保存在 pdata[Length]中，将 pdata[Length]中的随机数复制成 5 个副本，放置于 copy[5][Length]的二维数组里，每个副本对应一个排序算法，以保证在同一次程序的运行中各排序算法的对象是相同的随机数组。利用 time 类的 clock( ) 函数获得系统时间，用来计算出每个排序算法执行排序所需要的时间，以 ms 为单位，然后在命令控制台输出各排序排列同一个随机数组所需要的时间，用来比较各个算法。程序清单: #include #include #include #include using namespace std;

void Merge(int* data, int p, int q, int r); void MergeSort(int* data, int p, int r); void BubbleSort(int* data, int Count); void SelectSort(int* data, int Count); void Run(int* data, int left, int right); void QuickSort(int* data, int Count); void InsertSort(int* data, int Count); void CRandom(int* data, int l); void CountMergeSort(int* data); void CountBubbleSort(int* data); void CountSelectSort(int* data); void CountQuickSort(int* data); void CountInsertSort(int* data); const long Length = 10000; //定义随机数组长度 clock_t start,finish; //设置起始时间和完结时间变量 double total_time; //计算各排序函数运行时间的变量 int main() { int *pdata = new int[Length]; int * copy[5]; //新建二维数组用来保存随机数组副本 copy[0] = new int[Length]; copy[1] = new int[Length]; copy[2] = new int[Length]; copy[3] = new int[Length]; copy[4] = new int[Length]; CRandom(pdata, Length); //产生Length大小的随机数列，保存到pdata[]中 for (int j=0; j<5; j++) { } for(int k=0; k

//MergeSort START void Merge(int *data, int p, int q, int r) { int i, j, k, n1, n2; n1 = q - p + 1; n2 = r - q; int *L = new int[n1]; int *R = new int[n2]; for(i = 0, k = p; i < n1; i++, k++) { } L[i] = data[k]; for(i = 0, k = q + 1; i < n2; i++, k++) { } R[i] = data[k]; for(k = p, i = 0, j = 0; i < n1 && j < n2; k++) { if(L[i] > R[j]) { } else { } data[k] = L[i]; i++; data[k] = R[j]; j++; } if(i < n1) { } for(j = i; j < n1; j++, k++) { } data[k] = L[j]; if(j < n2) for(i = j; i < n2; i++, k++) { } data[k] = R[i]; { } }

void MergeSort(int *data, int p, int r) { } if(p < r) { } int q = (p + r) / 2; MergeSort(data, p, q); MergeSort(data, q + 1, r); Merge(data, p, q, r); //MergeSort END //BubbleSort START void BubbleSort(int* data,int Count) { int iTemp; for(int i=0;i

if(data[j]middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = data[i]; data[i] = data[j]; data[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(lefti)，递归右半边 if(right>i) Run(data,i,right);

void QuickSort(int* data,int Count) { } Run(data,0,Count-1); //QuickSort END //Insert START void InsertSort(int* data,int Count) { int temp; for(int i=1;i0&&temp

ms 为单位（下同） } void CountBubbleSort(int* data) { } start = clock(); BubbleSort(data, Length); finish = clock(); total_time = (double)(finish-start)/CLOCKS_PER_SEC; cout << "BubbleSort costs " << total_time * 1000 <<" ms." << endl; void CountSelectSort(int* data) { } start = clock(); SelectSort(data, Length); finish = clock(); total_time = (double)(finish-start)/CLOCKS_PER_SEC; cout << "SelectSort costs " << total_time * 1000 <<" ms." << endl; void CountQuickSort(int* data) { } start = clock(); QuickSort(data, Length); finish = clock(); total_time = (double)(finish-start)/CLOCKS_PER_SEC; cout << "QuickSort costs " << total_time * 1000 <<" ms." << endl; void CountInsertSort(int* data) { } start = clock(); InsertSort(data, Length); finish = clock(); total_time = (double)(finish-start)/CLOCKS_PER_SEC; cout << "InsertSort costs " << total_time * 1000 <<" ms." << endl;

实验结果: 1. 当 Length 为 1000 时: 可见在数组长度比较小的情况下，在我的 PC 上，各个算法的执行没有可以观察到的差别。执行了 5 次才出现一次冒泡排序不是 0 ms . 2. 当 Length 为 10000 时: 在数组长度为 10000 时，冒泡排序已经体现出速率上的略势，快速排序和归并排序表现出的执行速率比较高。 3. 当 Length 为 100000 时: 当数组大小达到 100000 的时候，冒泡排序明显力不从心，从时间的方面来说，快速排序的表现最好，其次是归并排序，然后是插入排序，接着是选择排序，冒泡最低效。

分享到：

赞收藏

资料库

算法排序实验报告包括对五种排序算法的算法实现时间的比较.doc

相关推荐

开发技术

热门标签

最新资料