careercup-排序和查找 11.1
浏览数：21 /
时间：2015年06月08日
11.1 给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B。编写一个方法，将B合并入A并排序。
解法：
已知数组A末端有足够的缓冲，不需要再分配额外空间。程序的处理逻辑很简单，就是逐一比较A和B中的元素，并顺序插入数组，直至耗尽A和B中的所有元素。这么做的唯一问题是，如果将元素插入数组A的前端，就必须将原来的元素往后移动，以腾出空间。更好的做法是将元素插入数组A的末端，那里都是空闲的可用空间。
下面的代码就是实现了上述做法，从数组A和B的末端元素开始，将最大的元素放到数组A的末端。
C++实现代码：
#include<iostream> using namespace std; void merge(int a[],int b[],int lastA,int lastB) { int i=lastA-1; int j=lastB-1; int k=lastA+lastB-1; while(i>=0&&j>=0) { if(a[i]>b[j]) { a[k--]=a[i--]; } else { a[k--]=b[j--]; } } while(j>=0) { a[k--]=b[j--]; } } int main() { int a[14]={1,3,5,7,9}; int b[7]={2,4,6,8,10,11,15}; merge(a,b,5,7); for(auto t:a) cout<<t<<‘ ‘; cout<<endl; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
