《算法排序问题实验报告材料》由会员分享，可在线阅读，更多相关《算法排序问题实验报告材料（11页珍藏版）》请在金锄头文库上搜索。
1、word排序问题求解实验报告一、 算法的根本思想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
4、low=privotkey do highhigh-1AlowAhigh /将比枢轴记录小的记录移到低端while lowhigh & Alow=pivotkey) do lowlow+1AhighAlow /将比枢轴记录大的记录移到高端AlowA0 /枢轴记录到位return low /返回枢轴位置二、 算法的理论分析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/
6、4。因此直接插入排序算法，在最优情况下的时间复杂度是 O(n)，在最坏情况下的时间复杂度为 O(n2)。2. 快速排序算法理论分析下面我们来分析快速排序的平均时间性能。 假设 T(n)为对 n 个记录 A1.n进展快速排序所需时间，如此由算法 QuickSort 可见：其中，Tpass(n)为对 n 个记录进展一趟快速排序 PartitionA,1,n所需的时间，从一趟快速排序算法可见，其和记录数 n 成正比，可以用 表示c 为某个常数；T(k-1)和 Tn-k分别为对 A1.k-1和 Ak+1.n中记录进展快速排序 QuickSortA,1,k-1和QuickSortA,k+1,n所需时间。
7、假设待排序列中记录是随机排列的，如此在一趟排序之后，k 取 1 至 n 之间任何一值的概率一样，快速排序所需时间的平均值如此为Tavg(n)=knInn，其中 n 为待排序序列中记录的个数，k 为某个常数。 通常，快速排序被认为是，在所有同数量级O(nlogn)的排序方法中，其平均性能最好。但是，假如初始记录序列按关键字有序或根本有序时，快速排序将蜕化为起泡排序，其时间复杂度为 O(n2)。三、 试验分析1、 试验环境2、 程序的执行1)由函数 datagenetare()生成 20000 个在区间1,100000上的随机整数，并将随机整数保存到数组 num，接着调用函数 WriteFile(
8、)将这些数输出到外部文件 data.txt 中。2)调用函数 ReadFile()从 data.txt 中读取数据，并将其保存到数组 num1中。接着对数组 num1 进展直接插入排序，并计算和记录其运行时间。最后，调用函数 WriteFile()将直接插入排序的结果写入 resultsIS.txt，并记录运行时间为 TimeIS。3)调用函数 ReadFile()从 data.txt 中读取数据，并将其保存到数组 num2中。接着对数组 num2 进展快速排序，并计算和记录其运行时间。最后，调用函数 WriteFile()将快速排序的结果写入 resultsQS.txt，并记录运行时间为 T
9、imeQS。3、 试验数据当N=20000时：当N=30000时：当N=40000时：当N=50000时：当N=60000时：当N=70000时：当N=80000时：4、 实验结果分析20000300004000050000600007000080000插入排序2.快速排序做出折线统计图四、 试验心得通过本次试验首先对在C+下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！五、 实验代码#include #include #include #include #include us
10、ing namespace std;const int NumS = 80000;void datagenetare(int num,int n); /产生随机数，保存到数组numvoid ReadFile(int num,char name);/读取名为name文件中的数据，保存到数组numvoid QuickSort(int arr, int n);/将数组arr中数据快速排序void InsertionSort(int arr,int n);/将数组arr中数据直接插入排序int main()int *num=(int *)malloc(sizeof(int)*NumS);int *nu
11、m1=(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;datagenetare(num,NumS); /产生随机数，保存到数组numcout.precision(6); /设置浮点数的显示精度cout.setf(ios_base:showpo
12、int); /输出末尾的/直接插入排序的分析ReadFile(num1,data.txt);/读取data.txt中的数据，保存到数组num1coutnInsertionSort Start .n;start_time1=clock(); /开始计时InsertionSort(num1,NumS); /直接插入排序数组num1中的数据end_time1=clock(); /完毕计时timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;coutThe Time-suption in InsertionSort is timeIS second
13、s!nn; /输出运行时间ofstream ocout;ocout.open(resultsIS.txt,ios:app);ocoutnThe Time-suption in InsertionSort is timeIS secondsn;ocout.close();elsecoutnCan not open resultsIS.txt!n;exit(1); /异常退出/快速排序的分析ReadFile(num2,data.txt); /读取data.txt中的数据，保存到数组num2coutQuickSort Start .n;start_time2=clock(); /开始计时QuickS
14、ort(num2,NumS); /快速排序数组num中的数据end_time2=clock(); /完毕计时timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;coutThe Time-suption in QuickSort is timeQS seconds:n; /输出运行时间ocout.open(resultsQS.txt,ios:app);ocoutnThe Time-suption in QuickSort is timeQS secondsn;ocout.close();elsecoutnCan not open resultsQS.tx
