基础算法之三: 合并两个有序数组

基础算法之三: 合并两个有序数组

算法思想:

将两个有序数组合并为一个有序数组,也就是对两个数组中的所有元素进行排序。

与一般排序所不同的是,各个数组都是排好序的,现在要做的是将各个排好序的数组进行归并,归并后,仍是有序的。

要设计这个归并数组的算法,须先找出其中蕴含的规律:

1) 对于同一个数组的各个元素,它们之间不用进行比较,因为它们是有序的

2) 需比较大小的两个元素必定是分处于不同数组

算法流程:

    
     A数组的第i个元素与B数组的第j个元素进行比较
    // 比较到这一步, 说明A中已经有i个元素保存到C中,B中已经有j个元素保存在C中,目前,C中已经保存了i+j个元素, 因此,下一个比较的结果要放入C[i+j]单元中

如果A[i]<B[j]

             C[i+j]= A[i];
             i++;

否则

             C[i+j]=B[j];   
             j++;

然后,再重新比较A[i]和B[j]的大小,因此,上段程序是需要不断循环的,循环结束标志是 A中所有元素或B中所有元素都已经保存到了C中。

 
   while(A中还有未遍历元素&&B中也还有未遍历元素){

如果A[i]<B[j]

             C[i+j]= A[i];
             i++;

否则

             C[i+j]=B[j];   
             j++;
} 
   while(A中还有未遍历的元素)
            C[j+i++]=A[i++];
 
  while(B中还有未遍历的元素)
           C[i+j++]=B[j++];

算法实例1 :

    // 合并有序数组  
    std::vector<int> A;  
    std::vector<int> B;  
    //   将元素按顺序置于A数组  
    //   将元素按顺序置于B数组  
      
    std::vector<int> C;   
    std::vector<int>::iterator i1=A.begin();  
    std::vector<int>::iterator i2=B.begin();  
      
    while(i1!=A.end()&&i2!=B.end())  
    {  
        if (*i1<*i2)  
        {  
            C.push_back(*i1);  
            i1++;  
        }else{  
            C.push_back(*i2);  
            i2++;  
        }  
    }  
      
    while(i1!=A.end())  
    C.push_back(*i1++);  
      
    while(i2!=B.end())  
    C.push_back(*i2++);  

算法实例2:

有如下定义:

    typedef struct{  
     double index;  
     double value1;  
     double value2;  
    } line;  
      
    std::vector<line> v1;  
    std::vector<line> v2;  
v1和v2中的元素都是都是按他index值的升序排列,index不重复。

现在想做一个v3,来合并v1和v2.

合并的规则如下:

1)合并完的v3的元素是按index的升序排列,且index不重复。

2) 如果v1和v2中的元素有相同的index,则合并为一个元素,则这个元素的value1设为v1的value1,value2设为v2的value2.

3)如果某个元素的index只存在于v1,那么这个元素的value2改写为0. 若某个元素的index只存在于v2,那么这个元素的value1改写为0.

    std::vector<line>::iterator i1 = v1.begin(), i2 = v2.begin();  
    while(i1 != v1.end() && i2 != v2.end())  
    {  
        if(i1->index == i2->index)  
        {  
            line t = { i1->index, i1->value1, i2->value2 }  
            v3.push_back(t);  
            ++i1;  
            ++i2;  
        }  
        else if(i1->index > i2->index)  
        {  
            i2->value1 = 0;  
            v3.push_back(*i2);  
            ++i2;  
        }  
        else  
        {  
            i1->value2 = 0;  
            v3.push_back(*i1);  
            ++i1;  
        }  
    }  
      
    while(i1 != v1.end())  
        v3.push_back(*(i1++));  
      
    while(i2 != v2.end())  
        v3.push_back(*(i2++))  

算法实例3:

    // 合并删除线 和 下划线 位置  
    Node node;  
    std::vector<Node> erasePosition;  
    std::vector<Node>::iterator i1=delPosition.begin(),i2=underLinePosition.begin();  
      
    while (i1!=delPosition.end()&&i2!=underLinePosition.end())  
    {  
        if (i1->nStart==i2->nEnd) // 合并  同时前进++  
        {  
            node.nStart=i2->nStart;  
            node.nEnd=i1->nEnd;  
            i1++;  
            i2++;  
      
            erasePosition.push_back(node);  
            continue;  
        }  
      
        if (i1->nEnd==i2->nStart)  
        {  
            node.nStart=i1->nStart;  
            node.nEnd=i2->nEnd;  
            i1++;  
            i2++;  
            erasePosition.push_back(node);  
            continue;  
        }  
      
      
        if (i1->nEnd<i2->nStart)  
        {  
            node=*i1;  
            i1++;  
            erasePosition.push_back(node);  
            continue;  
        }  
      
        if (i1->nStart>i2->nEnd)  
        {  
            node=*i2;  
            i2++;  
            erasePosition.push_back(node);  
            continue;  
        }  
    }  
      
      
    while(i1!=delPosition.end())  
        erasePosition.push_back(*(i1++));  
      
      
    while(i2!=underLinePosition.end())  
        erasePosition.push_back(*(i2++));  

如果此文对您有所帮助,还往点击一下以下网站:

360导航

2345导航