算法分析与设计实验报告-合并排序、快速排序.pdf

《算法分析与设计实验报告-合并排序、快速排序.pdf》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告-合并排序、快速排序.pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-WORD 格式-可编辑-专业资料-完整版学习资料分享-实验报告 课程 计算机算法设计与分析 实验名称 合并排序、快速排序 学号 姓名 实验日期：实验一 合并排序、快速排序 一实验目的（1）学习合并排序和快速排序算法的思想，掌握原理。（2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。二实验内容（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。（2）输入 10 个整数，运用快速排序的思想进行编程实现，输出正确的排序结果 三实验代码(1)合并排序源代码如下：#include/调用 setw#include /将 b0至 bright-left+1拷贝到 alef

2、t至 aright template void Copy(T a,T b,int left,int right)int size=right-left+1;for(int i=0;isize;i+)aleft+=bi;/合并有序数组 aleft:i,ai+1:right到 b,得到新的有序数组 b template void Merge(T a,T b,int left,int i,int right)int a1cout=left,/指向第一个数组开头 a1end=i,/指向第一个数组结尾 a2cout=i+1,/指向第二个数组开头 a2end=right,/指向第二个数组结尾 bcout=

3、0;/指向 b 中的元素 for(int j=0;ja1end)bbcout+=aa2cout+;continue;/如果第一个数组结束，拷贝第二个数组的元素到 b if(a2couta2end)bbcout+=aa1cout+;continue;/如果第二个数组结束，拷贝第一个数组的元素到 b if(aa1coutaa2cout)bbcout+=aa1cout+;continue;/如果两个数组都没结束，比较元素大小，把较小的放入 b else bbcout+=aa2cout+;-WORD 格式-可编辑-专业资料-完整版学习资料分享-continue;/对数组 aleft:right进行合并

4、排序 template void MergeSort(T a,int left,int right)T*b=new intright-left+1;if(leftright)int i=(left+right)/2;/取中点 MergeSort(a,left,i);/左半边进行合并排序 MergeSort(a,i+1,right);/右半边进行合并排序 Merge(a,b,left,i,right);/左右合并到 b 中 Copy(a,b,left,right);/从 b 拷贝回来 int main()int n;coutn;int*a=new intn;cout请输入相应的数字：;for(i

5、nt i=0;iai;MergeSort(a,0,n-1);cout排序结果:;for(int j=0;jn;j+)coutsetw(5)aj;coutendl;return 1;（2）快速排序源代码如下：#include#define MAX 10 int QuickSort(int a,int l,int r)int pivot;/枢轴 int i=l;int j=r;int tmp;pivot=a(l+r)/2;/取数组中间的数为枢轴 do while(aipivot)j-;/j 左移 if(i=j)tmp=ai;ai=aj;aj=tmp;/交换 ai和 aj i+;j-;-WORD 格式-可编辑-专业资料-完整版学习资料分享-while(i=j);if(lj)QuickSort(a,l,j);if(ir)QuickSort(a,i,r);return 1;int main()int arrayMAX;int i;cout请输入MAX 个整数:;for(i=0;iarrayi;QuickSort(array,0,MAX-1);cout快速排序后：endl;for(i=0;iMAX;i+)coutarrayi;coutendl;return 0;四实验结果 五总结与思考