算法排序问题实验报告

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

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

3、Partition,它的参数是一个数组 A1.n和两个指针 low、high,设枢轴为 pivotkey，则首先从 high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从 low 所指位置起向后搜索，找到第一个大于 pivotkey 的数，并将其移到高端，重复这两步直至 low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下：Partition ( A, low, high)A0Alow/用数组的第一个记录做枢轴记录privotkeyAlow/枢轴记录关键字while lowhigh /从表的两端交替地向中间扫描while low=

4、privotkey do highhigh-1AlowAhigh /将比枢轴记录小的记录移到低端while lowhigh & Alow=pivotkey) do lowlow+1AhighAlow /将比枢轴记录大的记录移到高端AlowA0 /枢轴记录到位return low /返回枢轴位置2、 算法的理论分析1. 直接插入排序算法理论分析从空间来看，直接插入排序只需要一个数的辅助空间；从时间来看，直接插入排序的基本操作为：比较两个关键字的大小和移动记录。先分析一趟直接插入排序的情况。伪代码InsertionSort 中 while 循环的次数取决于待插入的数与前 i-1 个数之间的关系。若

5、 AiA0,则在 while 循环中，待插入数需与有序数组 A1.i-1中 i-1 个数进行比较，并将 Ai-1中 i-1 个数后移。则在整个排序过程（进行 n-1 趟插入排序）中，当待排序数组中数按非递减有序排列时，则需进行数间比较次数达最小值 n-1,数不需要移动；反之，当待排序数组中数按非递增有序排列时，总的比较次数达最大值(n+2)(n-1)/2，数移动的次数也达到最大值(n+4)(n-1)/2。若待排序数组是随机的，即待排序数组中的数可能出现的各种排序的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行数间的比较次数和数的移动次数，约为 n2/4。因此直接插入

6、排序算法，在最佳情况下的时间复杂度是 O(n)，在最坏情况下的时间复杂度为 O(n2)。2. 快速排序算法理论分析下面我们来分析快速排序的平均时间性能。 假设 T(n)为对 n 个记录 A1.n进行快速排序所需时间，则由算法 QuickSort 可见：其中，Tpass(n)为对 n 个记录进行一趟快速排序 Partition（A,1,n）所需的时间，从一趟快速排序算法可见，其和记录数 n 成正比，可以用 cn 表示（c 为某个常数）；T(k-1)和 T（n-k）分别为对 A1.k-1和 Ak+1.n中记录进行快速排序 QuickSort（A,1,k-1）和QuickSort（A,k+1,n）所

7、需时间。假设待排序列中记录是随机排列的，则在一趟排序之后，k 取 1 至 n 之间任何一值的概率相同，快速排序所需时间的平均值则为Tavg(n)=knInn，其中 n 为待排序序列中记录的个数，k 为某个常数。 通常，快速排序被认为是，在所有同数量级（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为 O(n2)。3、 试验分析1、 试验环境WIN 32系统，VC6.02、 程序的执行1)由函数 datagenetare()生成 20000 个在区间1,100000上的随机整数，并将随机整数保存到数组 num，

8、接着调用函数 WriteFile()将这些数输出到外部文件 data.txt 中。2)调用函数 ReadFile()从 data.txt 中读取数据，并将其保存到数组 num1中。接着对数组 num1 进行直接插入排序，并计算和记录其运行时间。最后，调用函数 WriteFile()将直接插入排序的结果写入 resultsIS.txt，并记录运行时间为 TimeIS。3)调用函数 ReadFile()从 data.txt 中读取数据，并将其保存到数组 num2中。接着对数组 num2 进行快速排序，并计算和记录其运行时间。最后，调用函数 WriteFile()将快速排序的结果写入 results

9、QS.txt，并记录运行时间为 TimeQS。3、 试验数据当N=20000时：当N=30000时：当N=40000时：当N=50000时：当N=60000时：当N=70000时：当N=80000时：4、 实验结果分析20插入排序0.3250.7191.3972.1993.054.5715.46快速排序0.0030.0050.0080.010.0120.0110.013做出折线统计图4、 试验心得通过本次试验首先对在C+下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！5、 实验

10、代码#include #include #include #include #include using namespace std;const int NumS = 80000;void datagenetare(int num,int n); /产生随机数，保存到数组numvoid Write num,char name,int n); /输出数组num到data.txt文件void Read num,char name);/读取名为name文件中的数据，保存到数组numvoid QuickSort(int arr, int n);/将数组arr中数据快速排序void InsertionS

11、ort(int arr,int n);/将数组arr中数据直接插入排序int main()int *num=(int *)malloc(sizeof(int)*NumS);int *num1=(int *)malloc(sizeof(int)*NumS);int *num2=(int *)malloc(sizeof(int)*NumS);clock_t start_time1,end_time1,start_time2,end_time2;double timeQS=0,timeIS=0;coutCreate NumS random numbers from 1 to 100000endl;d

12、atagenetare(num,NumS); /产生随机数，保存到数组numWrite,data.txt,NumS); /输出数组到data.txt文件cout.precision(6); /设置浮点数的显示精度cout.setf(ios_base:showpoint); /输出末尾的/直接插入排序的分析Read,data.txt);/读取data.txt中的数据，保存到数组num1coutnInsertionSort Start .n;start_time1=clock(); /开始计时InsertionSort(num1,NumS); /直接插入排序数组num1中的数据end_time1=

13、clock(); /结束计时timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;coutThe Time-comsuption in InsertionSort is timeIS seconds!nn; /输出运行时间Write,resultsIS.txt,NumS); /排序后的数据输出到resultQS.txt/输出运行时间timeIS到resultsIS.txtofstream ocout;ocout.open(resultsIS.txt,ios:app);if(ocout.good() /打开resultsIS.txtocout

14、nThe Time-comsuption in InsertionSort is timeIS secondsn;ocout.close();elsecoutnCan not open resultsIS.txt!n;exit(1); /异常退出/快速排序的分析Read,data.txt); /读取data.txt中的数据，保存到数组num2coutQuickSort Start .n;start_time2=clock(); /开始计时QuickSort(num2,NumS); /快速排序数组num中的数据end_time2=clock(); /结束计时timeQS=(double)(end

15、_time2-start_time2)/CLOCKS_PER_SEC;coutThe Time-comsuption in QuickSort is timeQS seconds:n; /输出运行时间Write,resultsQS.txt,NumS); /排序后的数据输出到resultQS.txt/输出运行时间timeQS到resultsQS.txtocout.open(resultsQS.txt,ios:app);if(ocout.good() /打开resultsIS.txtocoutnThe Time-comsuption in QuickSort is timeQS secondsn;

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

17、,ios:trunc);int i=0;if(ocout.fail()exit(1); /打开文件失败，退出for(;in;i+)ocoutnumi ;if(i+1)%40=0|i=n-1) /每输出40个数，换一行ocoutn;ocout.close();/将文件中的数据输入到数组void Read *num,char name)string strLine;int i=0;char achLine300;const char* pchTok;ifstream icin;icin.open(name,ios:in); /打开名为name的文件while(icin.good()int i =

18、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.close();/快速排序的实现，从左向右递增排序void QuickSort(int *arr, int n)int L = 0;int R = n-1;int t = arrL; /区间的第一个数作为基准if(n=1) /数组中存在个或个数据时，函数返回return;/将数据分成两个区间while(LR) /区间内至少存在一个元素的情况while(LR&t=arrR) R-;/从右向左搜索，直到第一个小于t的数arrRarrL = arrR;while(LR&arrL=t) L+;/从左向右搜索，找到第一