合并排序：分段错误 Core Dumped

Question

我阅读了合并排序算法的理论，并在此基础上使用 STL Vector class 在 C++ 中编写了合并排序的实现。

我知道从互联网上关于归并排序的万亿篇文章中的任何一篇复制粘贴都可以解决这个问题，但我想自己尝试一下。

当我运行代码出现分段故障核心转储错误时，这是由递归函数未终止引起的。谁能帮我找出代码中的错误。

#include<iostream>
#include<vector>
void merge(std::vector<int>& arr,int last,int begin,int mid);
void mergeSort(std::vector<int>& arr,int begin, int last){ 
    std::cout<<"In merge sort";
    int mid; 
    if(begin<last){
      mid = (begin+last)/2;
      mergeSort(arr,begin,mid);
      mergeSort(arr,mid,last);
      merge(arr,last,begin,mid);
    } 
    return;
}
void merge(std::vector<int>& arr ,int last,int begin,int mid){
    if(last==begin){
        std::cout<<"Returned form finger";
        return; 
    }
    int b=begin,c=mid;
    std::vector<int> temp;
    while(b<mid&&c<last){
        if(arr[b]<arr[c]){
            temp.push_back(arr[b]);
            b++;
        }
        else{
            temp.push_back(arr[c]);
            c++;
        }
    }
    while(b<mid){temp.push_back(arr[b]);}
    while(c<last){temp.push_back(arr[c]);}
    arr.swap(temp);
    return;
}


int main(){
    std::vector<int> arr({2,4,1,5,3,6,2,4,3});   
    for(auto it=arr.begin();it!=arr.end();++it){
        std::cout<<*it<<' '; 
    }
    std::cout<<'\n';
   mergeSort(arr,0,8);
    for(auto it=arr.begin();it!=arr.end();++it){
        std::cout<<*it<<' '; 
    }
    return 0;
    }

我使用gcc 9.3.0版本，使用终端命令编译代码

$ gcc filename.cpp -lstdc++

分析代码后，我认为问题出在合并函数中，但我无法指出它在哪里。如果有人能帮助我，如果可能的话，建议一些优化我的代码的方法，这将很有帮助。

Answer 1

所以你的递归是错误的。在 main 中，您有一个包含九个元素的向量。

std::vector<int> arr({2,4,1,5,3,6,2,4,3});

然后你这样调用 mergeSort

mergeSort(arr,0,8);

所以mergeSort的第三个参数是你正在排序的向量的最后一个有效索引（最好使用arr.size() - 1）。换句话说，mergeSort 正在对 inclusive 范围 (0, 8).

进行排序

现在 merge_sort 你有这个

void mergeSort(std::vector<int>& arr,int begin, int last) { 
    ...
    mergeSort(arr,begin,mid);
    mergeSort(arr,mid,last);
    ...
}

回想一下归并排序是对包含范围（begin, last）进行排序。因此，您的递归将对两个包含范围 (begin,mid) 和 (mid,last) 进行排序。换句话说，mid 被包含了两次。

既然（非常令人钦佩）你想自己编写这个程序，我会让你自己找出解决办法。

Answer 2

除了其他答案之外，您的 merge 函数中还有一个严重的问题。用于将剩余元素复制到 temp 的代码如下所示：

while (b < mid) { temp.push_back(arr[b]); }
while (c < last) { temp.push_back(arr[c]); }

请注意，您永远不会增加 b 或 c 索引。这是一个无限循环，最终会运行内存不足调用 push_back。简单的修复是这样的：

while (b < mid) { temp.push_back(arr[b++]); }
while (c < last) { temp.push_back(arr[c++]); }

合并排序：分段错误 Core Dumped

Merge Sort: Segmentation error Core Dumped

c++

algorithm

sorting

stdvector