算法排序问题实验报告

1、排序问题求解实验报告一、算法的基本思想1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的， 记录数增 1 的有序序列。直接插入排序算法的伪代码称为 InsertionSort ，它的参数是一个数组 A1.n ，包含 了 n个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A)for i j 2 to ndo key j Ai /key表示待插入数/Insert Ai into the sorted sequence A1.i-1 j j i-1while j>0 and Aj>key do Aj+1 j

2、Aj j j j-1Aj+1 jkey2、快速排序算法思想快速排序算法的基本思想是， 通过一趟排序将待排序序列分割成独立的两部分， 其中一 部分记录的关键字均比另一部分记录的关键字小， 则可对这两部分记录继续进行排序， 以达 到整个序列有序。假设待排序序列为数组 A1.n ，首先选取第一个数 A0 ，作为枢轴( pivot )，然后 按照下述原则重新排列其余数： 将所有比 A0 大的数都排在它的位置之前， 将所有比 A0 小的数都排在它的位置之后， 由此以 A0 最后所在的位置 i 作为分界线， 将数组 A1.n 分成两个子数组 A1.i-1和 Ai+1.n。这个过程称作一趟快速排序。 通过递

3、归调用快速排序，对子数组 A1.i-1和 Ai+1.n 排序。一趟快速排序算法的伪代码称为 Partition, 它的参数是一个数组 A1.n 和两个指针 low 、high, 设枢轴为 pivotkey ，则首先从 high 所指位置起向前搜索，找到第一个小于 pivotkey 的数，并将其移到低端，然后从 low 所指位置起向后搜索，找到第一个大于 pivotkey 的数， 并将其移到高端，重复这两步直至 low=high 。最后，将枢轴移到正确的位 置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high)A0 jAlow/ 用数组的第一个记录做枢轴记录

4、privotkey j Alow/ 枢轴记录关键字while low<high / 从表的两端交替地向中间扫描 while low<high && Ahigh>=privotkey do highj high-1Alow jAhigh / 将比枢轴记录小的记录移到低端 while low<high && Alow<=pivotkey) do lowj low+1Ahigh jAlow / 将比枢轴记录大的记录移到高端Alow jA0 / 枢轴记录到位 return low / 返回枢轴位置二、算法的理论分析1. 直接插入排序算法理论

5、分析 从空间来看，直接插入排序只需要一个数的辅助空间；从时间来看，直接插入排序的基 本操作为：比较两个关键字的大小和移动记录。先分析一趟直接插入排序的情况。伪代码 InsertionSort 中 while 循环的次数取决于待插入的数与前 i-1 个数之间的关系。若 Ai<A0, 则在 while 循环中，待插入数需与有序数组A1.i-1中 i-1 个数进行比较，并将 Ai-1 中 i-1 个数后移。则在整个排序过程(进行 n-1 趟插入排序)中，当待排序 数组中数按非递减有序排列时， 则需进行数间比较次数达最小值 n-1, 数不需要移动； 反之， 当待排序数组中数按非递增有序排列时，

6、总的比较次数达最大值 (n+2)(n-1)/2 ，数移动的次 数也达到最大值 (n+4)(n-1)/2 。若待排序数组是随机的， 即待排序数组中的数可能出现的各种排序的概率相同， 则我们可取 上述最小值和最大值的平均值， 作为直接插入排序时所需进行数间的比较次数和数的移动次 数，约为n八2/4。因此直接插入排序算法，在最佳情况下的时间复杂度是 O(n) ，在最坏情况下的时间复杂度 为 0(n2)。2. 快速排序算法理论分析 下面我们来分析快速排序的平均时间性能。假设 T(n) 为对 n 个记录 A1.n 进行快速排序所需时间， 则由算法 QuickSort 可见： 其中， Tpass(n) 为

7、对 n 个记录进行一趟快速排序 Partition( A,1,n )所需的时间，从一趟快速排序算法可见，其和记录数n成正比，可以用表示(c为某个常数)；T(k-1)和T(n-k )分别为对 A1.k-1和 Ak+1.n 中记录进行快速排序 QuickSort (A,1,k-1 )和QuickSort ( A,k+1,n )所需时间。假设待排序列中记录是随机排列的，则在一趟排序之后， k 取 1 至 n 之间任何一值的概率相同，快速排序所需时间的平均值则为Tavg(n)=knInn ，其中 n 为待排序序列中记录的个数， k 为某个常数。通常，快速排序被认为是，在所有同数量级( 0(nlogn)

8、 )的排序方法中，其平均性能最 好。但是， 若初始记录序列按关键字有序或基本有序时， 快速排序将蜕化为起泡排序， 其时 间复杂度为0(n2)。三、试验分析1 、试验环境WIN 32 系统， VC6.02、程序的执行1) 由函数 datagenetare() 生成 20000 个在区间 1,100000 上的随机整数， 并将随机整数保 存到数组 num ，接着调用函数 WriteFile() 将这些数输出到外部文件 data.txt 中。2) 调用函数 ReadFile() 从 data.txt 中读取数据， 并将其保存到数组 num1 中。接着对数 组 num1 进行直接插入排序， 并计算和记

9、录其运行时间。 最后， 调用函数 WriteFile() 将直 接插入排序的结果写入 resultsIS.txt ，并记录运行时间为 TimeIS 。3) 调用函数 ReadFile() 从 data.txt 中读取数据， 并将其保存到数组 num2 中。接着对数 组 num2 进行快速排序， 并计算和记录其运行时间。 最后， 调用函数 WriteFile() 将快速排 序的结果写入 resultsQS.txt ，并记录运行时间为 TimeQS。3、试验数据当 N=20000 时：当 N=30000 时：当 N=50000 时：当 N=70000 时：4、实验结果分析2000030000400

10、0050000600007000080000插入排序（).3250.7191.3972.1993.054.5715.46快速排序（).0030.0050.0080.010.0120.0110.013做出折线统计图快速排序和插入排序时间比较四、试验心得通过本次试验首先对在C+下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！五、实验代码#in elude <iostream> #in elude <ctime>#in elude <estdlib>

11、; #in elude <fstream> #in elude <stri ng> using n amespaee std;const int NumS = 80000;void datage netare(i nt nu m,i nt n); /产生随机数，保存到数组numvoid WriteFile(i nt nu m,char n ame,i nt n); /输出数组num到data.txt 文件void ReadFile(i nt nu m,char n ame);读取名为name文件中的数据，保存到数组 numvoid QuickSort(int arr,

12、int n);将数组arr中数据快速排序void In serti on Sort(i nt arr,i nt n);/将数组arr中数据直接插入排序int mai n() in t * nu m=(i nt *)malloc(sizeof(i nt)*NumS);in t * nu m1=(i nt *)malloe(sizeof(i nt)*NumS);in t * nu m2=(i nt *)malloe(sizeof(i nt)*NumS);eloek_t start_time1,e nd_time1,start_time2,e nd_time2;double timeQS=0,tim

13、eIS=0;eout<<"Create "<<NumS<<" ran dom numbers from 1 to 100000"<<e ndl; datage netare( nu m,NumS); /产生随机数，保存到数组numWriteFile(num,"data.txt",NumS); /输出数组到 data.txt 文件eout.preeisio n(6); /设置浮点数的显示精度cout.setf(ios_base:showpo in t); /输出末尾的/ 直接插入排序的分析

14、ReadFile(num1,"data.txt");/ 读取 data.txt 中的数据，保存到数组 num1 cout<<"nInsertionSort Start n"start_time1=clock(); / 开始计时InsertionSort(num1,NumS); /直接插入排序数组 numl中的数据end_time1=clock(); / 结束计时 timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;cout<<"The Time-comsuption

15、 in InsertionSort is "<<timeIS<<" seconds!nn" / 输出运行时间WriteFile(num1,"resultsIS.txt",NumS); /排序后的数据输出到 resultQS.txt/ 输出运行时间 timeIS 到 resultsIS.txtofstream ocout; ocout.open("resultsIS.txt",ios:app); if(ocout.good() / 打开 resultsIS.txtocout<<"n

16、The Time-comsuption in InsertionSort is "<<timeIS<<" secondsn" ocout.close();elsecout<<"nCan not open resultsIS.txt!n"exit(1); / 异常退出/ 快速排序的分析ReadFile(num2,"data.txt"); /读取 data.txt 中的数据，保存到数组 num2cout<<"QuickSort Start n"start_tim

17、e2=clock(); / 开始计时QuickSort( nu m2,NumS); /快速排序数组 num中的数据end_time2=clock(); / 结束计时 timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;cout<<"The Time-comsuption in QuickSort is "<<timeQS<<" seconds:n" /输出运行时间WriteFile(num2,"resultsQS.txt",NumS); /排序

18、后的数据输出到 resultQS.txt/ 输出运行时间 timeQS 到 resultsQS.txt ocout.open("resultsQS.txt",ios:app); if(ocout.good() / 打开 resultsIS.txtocout<<"nThe Time-comsuption in QuickSort is "<<timeQS<<" secondsn" ocout.close();elsecout<<"nCan not open resultsQS.t

19、xt!n"exit(1); / 异常退出 return 0;void datagenetare(int *num,int n)int i;srand(unsigned)time(0); /srand() 种子发生器函数，还有 rand() 随机数生成器函 数for(i=0;i<n;i+) / 产生个到之间的随机数 numi=rand()%9999+1;printf("n");/ 将数组中的数据输出到文件void WriteFile(int *num,char name,int n)ofstream ocout;ocout.open(name,ios:trun

20、c);int i=0;if(ocout.fail()exit(1); / 打开文件失败，退出for(;i<n;i+)ocout<<numi<<" "if(i+1)%40=0|i=n-1) / 每输出 40 个数，换一行 ocout<<"n"ocout.close();/ 将文件中的数据输入到数组void ReadFile(int *num,char name)string strLine;int i=0;char achLine300;const char* pchTok;ifstream icin;icin.o

21、pen(name,ios:in); /打开名为 name的文件while(icin.good()int i = 0;while(getline(icin,strLine)strLine.copy(achLine,strLine.size(),0);achLinestrLine.size()='0'/ 每行中的元素以空格为标识断开转换为 int 类型后存入数组 pchTok = strtok(achLine, " ");while(pchTok != NULL)numi = atoi(pchTok);i+;pchTok = strtok(NULL, " "); icin.c