尧图网站建设 
一、【实验目的】1复习排序算法的实现过程2设计平均与最坏情况下时间复杂度的数据环境并理解相关含义3初步了解算法时间复杂度的分析方法。二、【实验内容】至少选择3种排序算法要求对每种排序算法设计2组数据其中一组为最坏情况一组为一般情况随机数据规模不能少于10000。记录不同情况下算法的实际运行时间同时分析算法最坏情况与平均情况的运行次数。三、实验源代码#includestdio.h #includetime.h #includestdlib.h void BubbleSort(int arr[], int n) {//冒泡排序 int i, j; for(i 0; i n; i) { for(j n - 1; j i; j--) { if(arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } void InserSort(int arr[], int n) {//直接插入排序 int i; for(i 0; i n - 1; i){ int end i; int tmp arr[i 1]; while(end 0){ if(tmp arr[end]){ arr[end 1] arr[end]; }else{ break; } end--; } arr[end 1] tmp; } } void SelectSort(int arr[], int n) {//选择排序 int begin 0, i; while (begin n){ int min begin; for(i begin; i n; i) { if(arr[min] arr[i]) { min i; } } int temp arr[min]; arr[min] arr[begin]; arr[begin] temp; begin; } } int main() { const int n 10000; int nor_arr[n], bad_arr[n], copy1[n], copy2[n]; int i; srand(time(NULL)); for(i 0; i n; i) { nor_arr[i] rand(); }//随机数组 for(i 0; i 10000; i) { bad_arr[i] 10000 - i; }//最坏情况 clock_t start, end; double time0; for(i 0; i 10000; i) { copy1[i] nor_arr[i]; }//复制数组 start clock(); BubbleSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(冒泡排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i){ copy2[i] bad_arr[i]; } start clock(); BubbleSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(冒泡排序最坏情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy1[i] nor_arr[i]; } start clock(); InserSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(直接插入排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy2[i] bad_arr[i]; } start clock(); InserSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(直接插入排序最坏情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy1[i] nor_arr[i]; } start clock(); SelectSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(选择排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy2[i] bad_arr[i]; } start clock(); SelectSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(选择排序最坏情况%.lf ms\n,time0); return 0; }四、实验结果五、实验分析与总结随便写点 GDPU|算法分析与设计 实验一 排序算法的效率分析
一、【实验目的】1复习排序算法的实现过程2设计平均与最坏情况下时间复杂度的数据环境并理解相关含义3初步了解算法时间复杂度的分析方法。二、【实验内容】至少选择3种排序算法要求对每种排序算法设计2组数据其中一组为最坏情况一组为一般情况随机数据规模不能少于10000。记录不同情况下算法的实际运行时间同时分析算法最坏情况与平均情况的运行次数。三、实验源代码#includestdio.h #includetime.h #includestdlib.h void BubbleSort(int arr[], int n) {//冒泡排序 int i, j; for(i 0; i n; i) { for(j n - 1; j i; j--) { if(arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } void InserSort(int arr[], int n) {//直接插入排序 int i; for(i 0; i n - 1; i){ int end i; int tmp arr[i 1]; while(end 0){ if(tmp arr[end]){ arr[end 1] arr[end]; }else{ break; } end--; } arr[end 1] tmp; } } void SelectSort(int arr[], int n) {//选择排序 int begin 0, i; while (begin n){ int min begin; for(i begin; i n; i) { if(arr[min] arr[i]) { min i; } } int temp arr[min]; arr[min] arr[begin]; arr[begin] temp; begin; } } int main() { const int n 10000; int nor_arr[n], bad_arr[n], copy1[n], copy2[n]; int i; srand(time(NULL)); for(i 0; i n; i) { nor_arr[i] rand(); }//随机数组 for(i 0; i 10000; i) { bad_arr[i] 10000 - i; }//最坏情况 clock_t start, end; double time0; for(i 0; i 10000; i) { copy1[i] nor_arr[i]; }//复制数组 start clock(); BubbleSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(冒泡排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i){ copy2[i] bad_arr[i]; } start clock(); BubbleSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(冒泡排序最坏情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy1[i] nor_arr[i]; } start clock(); InserSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(直接插入排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy2[i] bad_arr[i]; } start clock(); InserSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(直接插入排序最坏情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy1[i] nor_arr[i]; } start clock(); SelectSort(copy1, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(选择排序一般情况%.lf ms\n,time0); for(i 0; i 10000; i) { copy2[i] bad_arr[i]; } start clock(); SelectSort(copy2, n); end clock(); time0 ((double)(end - start)) * 1000 / CLOCKS_PER_SEC; printf(选择排序最坏情况%.lf ms\n,time0); return 0; }四、实验结果五、实验分析与总结随便写点