对多个有序数组,实现归并操作分析

访客 阅读:119 2020-10-15 09:18:56 评论:0

工作中遇到了多个有序链的归并操作,这里记录一下解决方法。方便后续使用。

归并的方法列2种:

(1) 堆排序, 或者胜利树。减少比较次数。效率高,实现比较麻烦。

 

(2) 普通方法,每次都需要比较。实现简单,一般用这个就可以。

 

 下面的代码是,普通的方法,支持多个有序数组的归并操作。

#include <stdio.h> 
#include <climits> 
#include <vector> 
struct NodeList{ 
    int *val;   //保存数据的值数组 
    int num;    //数据的个数 
    int curr;   //当前统计到的下标 
 
    NodeList(int n):num(n), curr(0){ 
        val = new int[n]; 
    }    
 
    ~NodeList(){ 
        if (val){ 
            delete [] val; 
            val = NULL; 
        }    
    }    
}; 
 
void print_sort(std::vector<NodeList*> ver){ 
    int len = 0; 
    int min_val = 0; 
    int min_idx = -1;  
     
    //多个有序数组进行归并操作 
    while((len = ver.size()) > 0){  
        min_val = INT_MAX; 
        min_idx = -1;  
        //选取当前轮次的最小值 
        for(int i = 0; i < len; ++i){ 
            if (ver[i]->curr >= ver[i]->num){ 
                ver.erase(ver.begin() + i);  
                break; 
            }    
     
            int tmp_val = ver[i]->val[ver[i]->curr]; 
            if (tmp_val <= min_val){ 
                min_val = tmp_val; 
                min_idx = i; 
            } 
        } 
 
        //打印 
        if (min_idx != -1){ 
            printf("%d\n", min_val); 
            ++(ver[min_idx]->curr); 
        } 
    } 
} 
 
int main(){ 
    //新建有序数组 
    NodeList a(2);  a.val[0] = 3;   a.val[1] = 4; 
    NodeList b(3);  b.val[0] = 1;   b.val[1] = 3;   b.val[2] = 5; 
    NodeList c(2);  c.val[0] = 4;   c.val[1] = 6; 
 
    //构建有序数组列表 
    std::vector<NodeList*> ver; 
    ver.push_back(&a); 
    ver.push_back(&b); 
    ver.push_back(&c); 
 
    //排序打印 
    print_sort(ver); 
    return 0; 
}

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
关注我们

扫一扫关注我们,了解最新精彩内容