合并在Int C ++数组上排序

Question

我正在尝试在int数组上创建一个程序merge-sort但是我一直在运行这个合并排序时遇到麻烦，它给了我一个段错误，但是我发现它没有任何问题。在void mergesort中，当我先放<= last时，如果没有则出现段错误，然后打印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

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

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 2

标准库已经实现了正确合并的函数：std::inplace_merge。实施改编自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;
}

Answer 3

建议1：

而不是那条线：

int temp[size];

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

int temp = new int[size];

一旦你完成了它

delete[] temp;

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

Answer 4

您的代码有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