计算机学院0101班吴晴 学号200101183000 printf("ItItMERGESORTttQUiCKsoRT\n"); printf("Rand: " ∥随机时的比较 for(il; <=MAX 1++) Ci=Ai=rando count(l, MAX, MERGESORT for(i=l; i <=MAX 1++) BO=A[; for(i-l; i<=MAX; i++)AO=C[] count(l, MAX, QUICKSORT printf("InNotDEC ∥排降序时的比较 for(i1; K<=MAX; i++)Ai=BO count(l, MAX, MERGESORT) for(i=l; K <=MAX; i++)AG=C count(l, MAX, QUICKSORT: printf("InNotINC: ) ∥增序时的比较 for(i=l; K<=MAX; 1++) Al=BIMAX-i+ll count(1, MAX, MERGESORT) for(i=l; i<=MAX; i++)AG=C[MAX-i+1l count(l, MAX, QUICKSORT: getcho 运行结果: MERGESORT QUICKSORT 517ms 322ms NotDeC 322ms 314ms NotINc 401ms 325ms 编程分析 获得的结果是一个非线性结果,个人认为与CPU频率,操作系统所分配的时间片有关有时 会出现不合常理的结果但总体来说快速排序法的运行速度要快于归并排序法一般数据集在 非减时的排序所用时间要小于非增时排序所用的时间后者与随机时排序所用的时间的关系 很难区分 二,算节上的草源录短路径算油仅求出了从草娜点到其它所有结 点的录短路径长度。在此基础上,扩光算油劝能,使得新算油在 找出这些录经路径长度的同肘,也能求出路径上的结点序列。(以 习题316为例) 思想:多增加两个数组,一个用于存放到目的结点最短路径上最后一个点的位置,另一个则作 为栈使用 #include<stdio. h> #includesfloat. h> #define n6 #define mAX Flt max float DIST[N+1 float COSTIN+lIN+1}={{-1,-1,-1,-1,-1,-1,-1} i-1, 0, 20, 15, MAX, MAX, MAX;计算机学院 0101 班 吴晴 学号:2001011830002 3/5 printf("\t\tMERGESORT\t\tQUICKSORT\n"); printf("Rand:"); //随机时的比较 for(i=1;i<=MAX;i++) C[i]=A[i]=rand(); count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) B[i]=A[i]; for(i=1;i<=MAX;i++) A[i]=C[i]; count(1,MAX,QUICKSORT); printf("\nNotDEC:"); //非降序时的比较 for(i=1;i<=MAX;i++) A[i]=B[i]; count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) A[i]=C[i]; count(1,MAX,QUICKSORT); printf("\nNotINC:"); //非增序时的比较 for(i=1;i<=MAX;i++) A[i]=B[MAX-i+1]; count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) A[i]=C[MAX-i+1]; count(1,MAX,QUICKSORT); getch(); } 运行结果: MERGESORT QUICKSORT Rand: 517ms 322ms NotDEC: 322ms 314ms NotINC: 401ms 325ms 编程分析: 获得的结果是一个非线性结果，个人认为与 CPU 频率，操作系统所分配的时间片有关,有时 会出现不合常理的结果,但总体来说快速排序法的运行速度要快于归并排序法.一般数据集在 非减时的排序所用时间要小于非增时排序所用的时间.后者与随机时排序所用的时间的关系 很难区分.. 二,算书上的单源最短路径算法仅求出了从单源点到其它所有结 点的最短路径长度。在此基础上，扩充算法功能，使得新算法在 找出这些最短路径长度的同时，也能求出路径上的结点序列。(以 习题 3.16 为例) 思想:多增加两个数组,一个用于存放到目的结点最短路径上最后一个点的位置,另一个则作 为栈使用. #include<stdio.h> #include<conio.h> #include<float.H> #define N 6 #define MAX FLT_MAX float DIST[N+1]; float COST[N+1][N+1]={ {-1,-1, -1, -1, -1, -1, -1}, {-1,0, 20, 15, MAX,MAX,MAX}