对 Int C++ 数组进行合并排序

Question

我试图在一个 int 数组上创建一个程序合并排序，但我一直遇到问题运行这个合并排序，它给了我一个段错误，但我找不到任何问题.在 void mergesort 中，当我先放 <= 最后时出现段错误，如果没有，则打印 5 5 5 5。

#include <iostream>

 using namespace std;


void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
    {
       temp[i] = arr[i];
    }
    int i=first, j=middle+1, k=0;
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
       {
          arr[k] = temp[i];
          i++;
       }
       else
       {
          arr[k]=temp[i];
          j++;
       }
       k++;
    }
    while(i<=middle)
    {
       arr[k]=temp[i];
       k++;
       i++;
    }
}

void mergesort(int *arr, int size, int first, int last)
{
    if(first<last)
    {
       int middle = ( first + last )/2;
       mergesort(arr,size,first,middle);
       mergesort(arr,size,middle+1,last);
       merge(arr,size,first,middle,last);
    }
}
int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers,size,0,9);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

Answer 1

建议 1：

而不是那一行：

int temp[size];

如果您需要动态大小的数组，请使用：

int temp = new int[size];

然后一旦你完成它

delete[] temp;

编辑：Neil 建议在这种情况下使用 std::vector 可能比数组更有用（如果您被允许使用它）。

Answer 2

有（至少）两个错误。这个：

else
{
   arr[k]=temp[i];                                          
   j++;
}

应该是这样的：

else
{
   arr[k]=temp[j];                                          
   j++;
}

还有这个：

int i=first, j=middle+1, k=0;

应该是这样的：

int i=first, j=middle+1, k=first;

一般来说，您应该学会单步执行代码，至少通过在各处放置诊断输出语句。一旦你掌握了它，你就可以升级到一个好的调试器。

Answer 3

您的代码有 3 个错误，如果需要，您也可以减少代码长度。

void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
      temp[i] = arr[i];
    int i=first, j=middle+1, k=first; // 1st Change, Set k to first instead of 0
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
          arr[k++] = temp[i++];
       else
          arr[k++]=temp[j++]; // 2nd Change, use j instead of i
    }
    while(i<=middle)
       arr[k++]=temp[i++];
    while(j<=last)    // 3rd Change you missed this case
        arr[k++]=temp[j++];
}

Live Code

Answer 4

标准库已经实现了正确合并的功能：std::inplace_merge. Implementation adapted from this more general post

void mergesort(int * first, int * last)
{
    std::ptrdiff_t N = std::distance(first, last);
    if (N <= 1) return;                   
    int * middle = std::next(first, N / 2);
    mergesort(first, middle); 
    mergesort(middle, last);  
    std::inplace_merge(first, middle, last); 
}

int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers, numbers+size);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

对 Int C++ 数组进行合并排序

Merge Sort on Array of Int C++

c++

arrays

sorting

int

mergesort