《算法设计与分析大作业报告》
班级： 学号： 姓名：
分治法大作业报告
问题陈述：
编程实现归并排序算法和快速排序算法，输出排序结果。输入10组相同的数据，验证排序结果和完成排序的比较次数。
分治法基本思想：
分治法的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题要容易些， 先得出子问题的解，由此得出原问题的解，这就是所谓“分而治之”的思想。
算法描述：
当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同
子集合，得到k个不同的可独立求解的子问题，其中1 1.归并排序的思想：将A（1），??，A（N）分成两个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含N个元素分好类的元素 2.快速排序的思想：选取A的某个元素做为划分元素，然后将其他元素重新排列，使在划分元素以前出现的元素都 小于或等于它，在划分元素之后出现的划分元素都大于等于它。 程序代码： #include void MergeSort(int *data,int x,int y,int *temp) { int p,q,m,i=x; if (y-x>1) {m = x+(y-x)/2; p = x; q = m; MergeSort(data,x,m,temp); MergeSort(data,m,y,temp); } while(p for(i=x;i data[i] = temp[i]; } if (q>=y||(p {temp[i++] = data[q++];} void HoareSort(int *data,int x,int y) { int p=x,q=y-1,temp; while(p while (q>p&&data[q]>=data[p]) q--; if (q>p) { } while(q>p&&data[p]<=data[q]) p++; temp = data[p],data[p] = data[q],data[q] =temp; p++; if (p if (p==q) { temp = data[p],data[p] = data[q],data[q] =temp; q--; HoareSort(data,x,p); }}} HoareSort(data,p+1,y); int main() { int data[10],i; int temp[10]; srand(time(NULL)); for (i=0;i<10;i++) { data[i] = rand()0; } printf(\未排序排序的数据为：\\n\ for (i=0;i<10;i++) {printf(\ printf(\ printf(\归并排序的顺序为： \\n\ MergeSort(data,0,10,temp); for (i=0;i<10;i++) {printf(\ printf(\ printf(\快速排序的顺序为： \\n\ HoareSort(data,0,10); for (i=0;i<10;i++) {printf(\ printf(\ return 0; } 运行结果： 结论分析： 归并排序和快速排序都是递归排序，但是归并排序是稳定的排序方法，快速排序是不稳定的排序方法。（1）此问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （2）利用该问题分解出的子问题的解可以合并为该问题的解； （3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。