《算法设计》课程报告--空间子数组换位算法

《《算法设计》课程报告--空间子数组换位算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《算法设计》课程报告课题名称：算法设计课题负责人名（学号）：--同组成员名单（角色）：指导教师：-评阅成绩：评阅意见：提交报告时间：2014年6月17日0(1)空间子数组换位算法计算机科学与技术专业学生--指导老师---［题目描述］a［0m-l］是一个有n个元素的数组，k(l彡k彡n-1)是一个非负整数。试设计一个算法将子数组a［0±-ll与a［k+Ln-ll换位。要求算法在最坏情况下耗吋0(n),且只川到0(1)的辅助空间［关键词］子数组0(1)空间O(n)时间［算法分析］采用分治算法当v［k］左边子数组的长度等于右边的子数组长度时，直接将两个子数组

2、对应的元素互换即可当左边子数组长度小于右边子数组长度吋，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数通过分析，可知只需耍利用保存元素对换时的交换空间即可，空间复杂度为0(1)，子数组对换时时间复杂度不会超过O(n)［程序实现］^includeh>^include^include〈vector〉^include〈iostream〉usingnamespacestd;//对应互换v的left

3、_low-left_high和right_low-right_highvoidSwap(vector&v,intleft_low,intleft_high,intright_low,intright_high){inttemp;while(leftjow<=left_high){temp=v[left_low];v[left_low]二v[right_low];v[right_low]二temp;++left_low;++right_low;return;//分治算法，每次选最小的子数组对应交换voidExchange(vector

4、&v,intk,intlow,inthigh){if(low

5、w-k-1,k+1,high);Exchange(v,k,high+low-k,high);}}return;}intmain(){vectorv;intn,k;while(scanf("%d%d"，&n：&k)=2){v.resize(n);for(inti=0;i〈n;++i){scanfdcf'，&v[i]);printf('"Beforeexchangesubarray:〃)；for(intj=0;j〈n;++j){printf("%d〃，v[j]);}printf("〃)•，Exchange(v,k,0,n-1);print

6、f(〃Afterexchangesubarray:〃)；for(intk=0;k〈n;++k){printf("%d〃，v[k]);}printfC〃)•，}return0;}[运行结果]'C:UsersAdminiytratorDesktophome算法Si十作业wod1030123456789Beforeexcbangesubarray:0123456789Afterexchangesubarray：4567890123参考文献[1]王晓东.计算机算法设计与分析.~3版北京:电子工业出版社2007.5