合并两个有序数组（C++）-白红宇

合并两个有序数组（C++）

阅读量：5297 次

发布时间：2019-06-14

本文共 1925 字，大约阅读时间需要 6 分钟。

合并两个有序数组

思路

存在一个数组为空，则直接返回另一个非空数组。

都不为空

两个数组都非空：记两个数组分别为v1,v2，合并后的数组为vc，设置两个指针i、j分别指向数组v1,v2，令i=j=0，

若v1[i] <= v2[j]，则可以一直添加v1的元素到合并后的数组vc知道条件不满足,同时修改i；

添加v2的元素到vc；

如果一个数组被遍历完，则应该终止；

添加未遍历完的数组的其余元素到vc。

代码

1 vector
     
       merge(vector
      
        &v1, vector
       
         &v2) 2 { 3     if(v1.empty()) return v2; 4     if(v2.empty()) return v1; 5      6     vector
        
          r; 7     unsigned int i = 0,j = 0; 8     while(i < v1.size() && j < v2.size()) 9     {10         while(v1[i]<=v2[j] && i < v1.size())11         {12             r.push_back(v1[i]);13             i++;14         }15         while(v1[i]>=v2[j] && j < v2.size())16         {17             r.push_back(v2[j]);18             j++;19         }20     }21     while(i

测试代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 void printVec(const vector
        
          &v) 6 { 7     for(auto &x: v) 8         cout << x << ' '; 9     cout << endl;10 }11 12 // 每次遍历使当前元素最小，第二次为次最小,...13 vector
         
           sortAscend(vector
          
            &v)14 {15 vector
           
             r = v;16 for(size_t i = 0; i < r.size(); i++)17 {18 for(size_t j = i+1; j < r.size(); j++)19 {20 if(r[i] > r[j])21 {22 int t = r[j];23 r[j] = r[i];24 r[i] = t;25 }26 }27 // printVec(r);28 }29 return r;30 }31 32 int main()33 {34 std::vector
            
              v1 = { 7, 5, 16, 5, 8, 1,2}, v1r;35 std::vector
             
               v2 = { 3,3,6,3,0,1,0}, v2r;36 v1r = sortAscend(v1);37 cout << "-----------------------------" << endl;38 v2r = sortAscend(v2);39 vector
              
                r = merge(v1r, v2r);40 printVec(v1r);41 printVec(v2r);42 printVec(r);43 assert(r.size() == v1r.size()+v2r.size());44 }