合并、快速排序实验报告.doc

《合并、快速排序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、合并、快速排序一．实验目的：1.理解算法设计的基本步骤及各部的主要内容、基本要求；2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；3.通过本次试验初步掌握将算法转化为计算机上机程序的方法。二．实验内容：1.设计和实现递归的合并排序算法、快速排序算法；2.设计和实现消除递归的合并排序算法、快速排序算法；3.设计有代表性的典型输入数据，分析算法的效率；4.对于给定的输入数据，给出算运行结果和运行结果，并给出实验结果分。三．实验操作：1.合并排序思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的思想，是一种稳定的排序方法。将以有序的子序列合

2、并，得到完全有序的序列；及先使每个字序列有序，再使子序列段间有序。归并过程：比较数组中两个元素的大小，如比较a[i]和a[j]的大小，若a[i]<=a[j]，将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表剩下的元素复制到r中从下标k到下标t的单元。如：6，202，100，301，38，8，1第一次归并：{6，202}，{100，301}，{8，38}，{1}第二次归并：{6，100，202，301}，{1，8，38}第三次归并：{1，6，8，38，100，202，301}合并排序算法：voidme

3、rge(intArray[],intlow,inthigh){inti=low,j,k;intmid=(low+high)/2;j=mid+1;k=low;int*list=newint[high+1];while(i<=mid&&j<=high){if(Array[i]<=Array[j])list[k++]=Array[i++];elselist[k++]=Array[j++];}while(i<=mid)list[k++]=Array[i++];while(j<=high)list[k++]=Array[j++];for(intn=low;n<=high;n++)Arra

4、y[n]=list[n];}voidmergeSort(intArray[],intlow,inthigh){if(low

5、生变动。快速排序的过程：1）设置两个变量i,j，排序开始的时候：i=0,j=N-1（N为元素个数）；2）以第一个数组元素作为关键数据，赋给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；如：下标012345原始数据627389第一次快排267389第二次快排237689第三次快排236789快速排序的算法：voidQsort(intList[],i

6、ntlow,inthigh){if(low>=high)return;intfirst=low;intlast=high;intkey=List[first];while(first=key)--last;List[first]=List[last];while(first

7、;}2.实验数据的输入：本实验采用将数据输入与输出存储到文件中的方式，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin流输入来控制数据的输入。对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数据存入到另一文件之中。由于输入需要大量的数据，可采用从“随机数.txt”中读取数据。文件输入算法：intinput(){ofstreamoutFile;outFile.open("E://程序设计/practice1/算法设计