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

《算法设计》课程报告 课题名称： 算法设计 课题负责人名（学号）： -- 同组成员名单（角色）： -- 指导教师： --- 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 17 日  O(1)空间子数组换位算法 计算机科学与技术 专业 学生 -- 指导老师 --- [题目描述] a[0:n-1]是一个有 n 个元素的数组， k(1≤k≤n-1)是一个非负整数。试设计一个算法将子数组 a[0:k-1]与 a[k+1:n-1]换位。要求算法在最坏情况下耗时 O(n)，且只用到 O(1)的辅助空间 [关键词] 子数组 O(1)空间 O(n)时间 [算法分析] 采用分治算法 当v[k]左边子数组的长度等于右边的子数组长度时，直接将两个子数组对应的元素互换即可 当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数 当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数 通过分析，可知只需要利用保存元素对换时的交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超过O(n) [程序实现] #include stdio.h #include stdlib.h #include vector #include iostream using namespace std; //对应互换v的left_low-left_high 和 right_low - right_high void Swap(vectorint v,int left_low,int left_high,int right_low,int right_high){ int temp; while(left_low = left_high){ temp = v[left_low]; v[left_low] = v[right_low]; v[right_low] = temp; ++left_low; ++right_low; } return; } //分治算法，每次选最小的子数组对应交换 void Exchange(vectorint v,int k,int low,int high){ if(lowhigh){ if((k-low+1)==(high-k)){//v[k]左右两个子数组长度相等，直接互换 Swap(v,low,k,k+1,high); } else if((k-low+1)(high-k)){//v[k]左边子数组长度小于右边子数组，将左边的子数组互换到右边子数组的右边 Swap(v,low,k,low+high-k,high); Exchange(v,k,low,low+high-k-1); } else{ //v[k]右边子数组换到左边子数组前部分 Swap(v,low,high+low-k-1,k+1,high); Exchange(v,k,high+low-k,high); } } return; } int main(){ vectorint v; int n,k; while(scanf(%d%d,n,k)==2){ v.resize(n); for(int i=0;in;++i){ scanf(%d,v[i]); } printf(Before exchange subarray:\n); for(int j=0;jn;++j){ printf(%d ,v[j]); } printf(\n); Exchange(v,k,0,n-1); printf(After exchange subarray:\n); for(int k=0;kn;++k){ printf(%d ,v[k]); } printf(\n); } return 0; } [运行结果] 参考文献 [] 王晓东.计算机算法设计与分析.--3版.--北京：电子工业出版社2007.5 课程名称： 学生姓名： 学生学号： -2- -1-