时间戳

首页 > 解决方案 > 合并排序：分割错误核心转储

c++ - 合并排序：分割错误核心转储

问题描述

我阅读了归并排序算法的理论，并在此基础上使用 STL Vector 类在 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++

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

标签： c++algorithmsortingstdvector

解决方案

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

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

你mergeSort这样打电话

mergeSort(arr,0,8);

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

现在merge_sort你有这个

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

回忆归并排序是对包含范围（开始，最后）进行排序。所以你的递归将对两个包含范围（开始，中间）和（中间，最后）进行排序。换句话说mid，被包含两次。

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

推荐阅读