08500329雷雷-算法实验一.doc

算法分析与设计实验日志指导教师 代宇 实验时间： 2010 年10月19日学院 计算机 专业 计算机科学与技术 班级 0410801 学号 08500329 姓名 雷雷 实验室 S308 实验题目：分治法实验目的：1 掌握分治法思想；2 熟练运用分治法解决相应的问题。实验要求：3 写一个“由底向上”的归并分类排序算法。4 用快速分类算法对10个数（键盘输入）进行从大到小或从小到大的排列并输出结果。实验主要步骤：第一题：#include#includeusing namespace std;void combine(int *,int,int,int);void mergesort(int *sortarray,int low,int high)int k=(low+high)/2;if(lowk和k+1-high这两段合并到low到high/把有序的两段数组合并为一段数组，并使合并这段数组同样有序void combine(int *sortarray,int low,int k,int high)vector temp(high-low+1,0); /temp是辅助存储数组，辅助存储当前排好序的状态int i,j,p;i=low;/控制前半段下标移动j=k+1;/控制后半段下标移动p=0; /控制temp的小标移动while(i=k&j=high)/但前半段或者后半段的数全部排好序（放入temp数组）时退出if(*(sortarray+i)*(sortarray+j) /从小到大排序tempp=*(sortarray+i);i+;elsetempp=*(sortarray+j);j+;p+;/把前半段没有排好序的数排序，放入temp数组while(ihigh)tempp=*(sortarray+i);i+;p+;/把后半段没有排好序的数排序，放入temp数组while(jk)tempp=*(sortarray+j);j+;p+;/把temp数组中的数拷贝会需要排序的数组，完成归并for(i=0;ihigh-low+1;i+)*(sortarray+low+i)=tempi;int main()int sortarray10=0;int num,low,high;/num是需要排序的个数，low和high控制排序的数据段int i=0;/freopen(stdin.txt,r,stdin);coutnum;for(i=1;i=num;i+)cout请输入数：*(sortarray+i);cout输入最小最大的个数：lowhigh;cout初始数据为:endl;for(i=1;i=num;i+)cout*(sortarray+i) ;coutendl;/进行归并排序mergesort(sortarray,low,high);cout从小到大排序后的数据为:endl;for(i=1;i=num;i+)cout*(sortarray+i) ;coutendl;return 0;、第二题：#include#include#includeQuickSort.husing namespace std;int main()int n;cout请输入你要排序的个数：n;vector a(n+1,0); cout请输入数：endl; for(int i=1;iai;cout由小到大排序结果为：endl;quicksort sorta(a);sorta.show();return 0;#ifndef QUICKSORT_H#define QUICKSORT_H#includeusing namespace std;class quicksortprivate:vector &sortarray;int partition(int low,int high)sortarray0=sortarraylow;while(lowhigh)while(low=sortarray0)high-;sortarraylow=sortarrayhigh;while(lowhigh&sortarraylow=sortarray0)low+;sortarrayhigh=sortarraylow;sortarraylow=sortarray0;return low;void qsort(int low,int high)if(lowhigh)sortarray0=partition(low,high);qsort(low,sortarray0-1);qsort(sortarray0+1,high);public:quicksort(vector &sortarr):sortarray(sortarr)qsort(1,sortarray.size()-1);void show()for(int i=1;isortarray.size();i+)if(i=sortarray.