分配内存时合并排序逻辑失败。

我正在研究一种合并排序的实现，它将按照歌曲的长度对歌曲列表进行排序。 我写了以下内容，并且无法理解我的逻辑中的缺陷。 这些函数不是返回一个排序列表，而是从原始列表的中间返回一个项目的列表。

vector<song> merge( vector<song> firstList, vector<song> secondList){
 vector<song> outPut;
 int i = 0; int n = 0;
 while( outPut.size() < (firstList.size() + secondList.size()-1 )){
    if( firstList[i].length < secondList[n].length){
        outPut.push_back( firstList[i]);
        i++;
    }else{
        outPut.push_back( secondList[n]);
        n++;
    }
 }
return outPut;
}
vector<song> mergeSortLength( vector<song> playlist){
 int scope = playlist.size()/2;
 vector<song> firstHalf( &playlist[0], &playlist[scope]);
 vector<song> secondHalf( &playlist[scope], &playlist[playlist.size()]);
 if ( firstHalf.size() != 1){
    firstHalf = mergeSortLength(firstHalf);
 }
 if ( secondHalf.size() != 1){
    secondHalf = mergeSortLength( secondHalf);
 }
 return merge( firstHalf, secondHalf);
}

如果我改变while循环条件

( outPut.size() < (firstList.size() + secondList.size() -1)){ 

至

( outPut.size() < (firstList.size() + secondList.size())){

尽管列表排序成功，但直到编译器吐出为止：

playList（27898,0x7fff78b7b000）malloc： * mach_vm_map（size = 7526769998340063232）失败（error code = 3）*错误：无法分配区域***在malloc_error_break中设置断点以调试libc ++ abi.dylib：以未捕获类型std :: bad_alloc的异常：std :: bad_alloc中止陷阱：6

我非常感谢任何人的帮助。 盯着这看，我的眼睛模糊不清。

---

在merge（）中，代码不检查是否已到达vector的末尾，具体来说，如果i> = firstList.size（）或n> = secondList.size（），则在这种情况下，另一个矢量将被复制。 while语句在结尾处不应该有-1。

VS抱怨使用＆playlist [playlist.size（）]创建临时向量，因为下标超出范围。 一个可选的方法是使用begin（）+ index，它是一个迭代器：

    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, 
                 playlist.begin()+playlist.size());

这已经过了一天了，所以发布一个固定版本以防万一有兴趣。 所有这些向量创建和推回都会增加很多开销，所以最好先做一次分配，然后使用迭代器或索引来处理子向量。

vector<song> merge( vector<song> firstList, vector<song> secondList){
    vector<song> outPut;
    size_t i = 0; size_t n = 0;
    while( outPut.size() < (firstList.size() + secondList.size()) ){
        if( firstList[i].length < secondList[n].length){
            outPut.push_back( firstList[i]);
            if(++i >= firstList.size()){
                do
                    outPut.push_back( secondList[n]);
                while(++n < secondList.size());
                break;
            }
        }else{
            outPut.push_back( secondList[n]);
            if(++n >= secondList.size()){
                do
                    outPut.push_back( firstList[i]);
                while(++i < firstList.size());
                break;
            }
        }
    }
    return outPut;
}

vector<song> mergeSortLength( vector<song> playlist){
    size_t scope = playlist.size()/2;
    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, playlist.begin()+playlist.size());
    if ( firstHalf.size() != 1){
        firstHalf = mergeSortLength(firstHalf);
    }
    if ( secondHalf.size() != 1){
        secondHalf = mergeSortLength( secondHalf);
    }
    return merge( firstHalf, secondHalf);
}

---

我没有看到很多关注，但也许你想

vector<song> secondHalf( &playlist[scope+1], &playlist[playlist.size()-1]);

＆playlist [playlist.size（）] without -1我认为是您的问题的根源，但我没有尝试过。

链接地址: http://www.djcxy.com/p/53491.html

上一篇: Merge sort logic failure in allocating memory.

下一篇: Implement algorithm to merge sorted arrays and return it