首页 > 代码库 > 关于归并排序的问题
关于归并排序的问题
课程设计用归并排序出现了一些有趣的问题, 首先是B题, 配套的代码第41行S相当于临时空间,
1 #include <iostream> 2 using namespace std; 3 #define MAXSIZE 1000001 4 typedef struct 5 { 6 int key; 7 }RedType; 8 9 typedef struct10 {11 RedType *r;12 int length;13 }SqList;14 15 void Create_Sq(SqList &L,int n)16 {17 int i; 18 for(i=1;i<=n;i++)19 {20 scanf("%d",&L.r[i].key);21 L.length++;22 }23 }24 void Merge(RedType R[],RedType T[],int low,int mid,int high)25 { 26 int i,j,k;27 i=low; j=mid+1;k=low; 28 while(i<=mid&&j<=high)29 { 30 if(R[i].key<=R[j].key) T[k++]=R[i++]; 31 else T[k++]=R[j++]; 32 } 33 while(i<=mid) 34 T[k++]=R[i++]; 35 while(j<=high) 36 T[k++]=R[j++]; 37 }38 void MSort(RedType R[],RedType T[],int low,int high)39 { 40 int mid;41 RedType *S=new RedType[MAXSIZE];42 if(low==high) T[low]=R[low]; 43 else44 { 45 mid=(low+high)/2; 46 MSort(R,S,low,mid); 47 MSort(R,S,mid+1,high); 48 Merge(S,T,low,mid,high); 49 }50 delete []S;51 } 52 void MergeSort(SqList &L)53 { 54 MSort(L.r,L.r,1,L.length); 55 } 56 void show(SqList L)57 {58 int i;59 printf("%d",L.r[1].key);60 for(i=2;i<=L.length;i++)61 printf(" %d",L.r[i].key); 62 printf("\n");63 }64 int main() 65 { 66 int n; 67 while(scanf("%d",&n)&&n!=0)68 { 69 SqList R; 70 R.r=new RedType[MAXSIZE+1]; 71 R.length=0; 72 Create_Sq(R,n); 73 MergeSort(R); 74 show(R); 75 }76 return 0;77 }
没有第50行 delete []S;这一行时内存超限.加上后提交结果如下.
| 运行编号 | 用户 | 问题 | 结果 | 内存 | 耗时 | 语言 | 代码长度 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| 23305 | tuhao | B | 正确 | 75732 | 15120 | C++/Edit | 1669 B | 2014-06-16 11:45:19 |
但是在数据加强的C题依然是内存超限, 注意到第41行的new反复调用导致MLE,能不能减少这方面的使用呢?
首先直接的方式把S改成外部(全局)数组, 但是这样是不行的, 这里指出一下原因,因为S为全局数组,递归调用下去将出现merge(S, S)的情况.
下面给出我的一个方法
1 //算法8.11 归并排序 2 #include <iostream> 3 using namespace std; 4 #define MAXSIZE 1000000 //顺序表的最大长度 5 typedef struct 6 { 7 int key; 8 char *otherinfo; 9 }RedType;10 11 typedef struct12 {13 RedType *r;14 int length;15 }SqList;16 17 RedType S[MAXSIZE]; 18 void Create_Sq(SqList &L,int n)19 {20 int i; //输入个数21 for(i=1;i<=n;i++)22 {23 scanf("%d",&L.r[i].key);24 L.length++;25 }26 }27 28 //用算法8.10 相邻两个有序子序列的归并29 void Merge(RedType R[],RedType T[],int low,int mid,int high)30 { 31 //将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high] 32 int i,j,k;33 i=low; j=mid+1;k=low; 34 while(i<=mid&&j<=high)35 { 36 //将R中记录由小到大地并入T中 37 if(R[i].key<=R[j].key) T[k++]=R[i++]; 38 else T[k++]=R[j++]; 39 } 40 while(i<=mid) //将剩余的R[low..mid]复制到T中 41 T[k++]=R[i++]; 42 while(j<=high) //将剩余的R[j.high]复制到T中 43 T[k++]=R[j++];44 for(i = low; i <= high; i++)45 R[i] = T[i];46 }//Merge 47 48 void MSort(RedType R[],int low,int high)49 { 50 //R[low..high]归并排序后放入T[low..high]中 51 int mid;52 53 if(low < high) {54 mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid 55 MSort(R,low,mid); //对子序列R[low..mid] 递归归并排序，结果放入S[low..mid] 56 MSort(R,mid+1,high);57 //对子序列R[mid+1..high] 递归归并排序，结果放入S[mid+1..high] 58 Merge(R, S, low,mid,high);59 60 }//else 61 }// MSort 62 63 void MergeSort(SqList L)64 { 65 //对顺序表L做归并排序 66 MSort(L.r,1,L.length); 67 }//MergeSort 68 void show(SqList &L)69 {70 int i;71 printf("%d",L.r[1].key);72 for(i=2;i<=L.length;i++)73 printf(" %d",L.r[i].key); 74 printf("\n");75 }76 77 int main() 78 { 79 SqList R;80 R.r=new RedType[MAXSIZE+1];81 int n; 82 while(scanf("%d",&n)&&n!=0){ 83 R.length=0; 84 Create_Sq(R,n); 85 MergeSort(R); 86 show(R); }87 return 0;88 }
做的改动很小
(1) 第17行, S为全局数组, 只有一个,无须递归分配
(2)修改MSort(RedType R[],int low,int high), 原来是四个参数,现在是三个, 即将R的low 至high区间元素归并到R中
(3)修改Merge,多了44,45行, 先将两部分R的内容归并到S,然后拷贝回R, 当然这个拷贝的开销是我们不期望的.
进一步的话题:
我们还可以取消拷贝的开销, 怎么做?可以考虑两个数组R,S, R->S->R->S->..., R归并到S,S归并到R, 滚动进行,实现起来按自底向上容易一些, 但是自顶向下的递归实现不是很直观,建议同学们尝试一下.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。