合并排序算法不起作用（c++），面临输出没有意义的问题

Question

我正在解决一个问题，我使用的是与归并排序相同的递归方法。但它没有给出所需的输出，所以我决定先实现基本的合并排序，我想我在递归算法中遗漏了一些东西

这是我的合并排序，虽然我怀疑这里有什么问题，但如果你需要它作为参考：

void mergeSort(int arr[], int l, int r)  
{
    if (l < r)    
    {        
        int m = l+(r-l)/2;            
        // Sort first and second halves    
        mergeSort(arr, l, m);    
        mergeSort(arr, m+1, r);    
        // merge both the sorted array    
        merge(arr, l, m, r);    
    }    
}

现在我认为合并功能不完整或不正确：

void merge(int arr[], int l, int m, int r)
{
     //these are going to be the iterators for our left, right and our final output array respectively
     int i = 0, j = 0, k = 0;
     // n1 is the size of the first array which is going to be one more than the differene of the mid index number and the first indexing number of the complete array
     int n1 = m - l + 1;
     // n2 is the size of the second array and the index of this array is starting from m + 1th element of the complete array
     int n2 = r - m;
     int L[n1];
     int R[n2];
     // populate the left array with elements upto n1 - 1th element of the array
     for (int x = 0; x < n1; x++)
     {
        L[x] = arr[x];
     }
     //populate the right array
     for (int x = 0; x < n2; x++)
     {
         R[x] = arr[x + n1];
     }
     while (i < n1 && j < n2)
     {
         if (L[i] <= R[j])
         {
             arr[k] = L[i];
             i++;
             k++;
         }
         else
         {
             arr[k] = R[j];
             j++;
             k++;
         }
     }
}

我做错了什么？

Answer 1

嗯，你的代码中有一些错误。

你应该在 merge 函数中从较低的索引开始获取元素，在左半部分：

L[x] = arr[l+x];
你也需要同样的右半部分:

R[x] = arr[m+x+1];
在merge函数中进行比较时，如果数组长度不同，你应该完成扫描：

while(i < n1){ arr[k++] = L[i++]; }

while(j
至少但不是最后，你应该从较低的索引开始填充数组，而不是总是从 0:

int i = 0, j = 0, k = l;

修改后的最终代码如下：

#include <stdio.h>
void merge(int arr[], int l, int m, int r){

 int i = 0, j = 0, k = l;
 int n1 = m - l + 1;

 int n2 = r - m;
 int L[n1];
 int R[n2];

 for (int x = 0; x < n1; x++)
 {
    L[x] = arr[l+x];
 }

 for (int x = 0; x < n2; x++)
 {
     R[x] = arr[m+x +1];
 }
 while (i < n1 && j < n2)
 {
     if (L[i] <= R[j])
     {
         arr[k] = L[i];
         i++;
         k++;
     }
     else
     {
         arr[k] = R[j];
         j++;
         k++;
     }
 }
 
 while(i < n1){
     arr[k++] = L[i++];
 }
 
 while(j <n2){
     arr[k++] = R[j++];
 }
}

 void mergeSort(int arr[], int l, int r)  {
  if (l < r){        
    int m = l+(r-l)/2;            

    mergeSort(arr, l, m);    
    mergeSort(arr, m+1, r);    

    merge(arr, l, m, r);    
  }    
}

void main(){
  int arr[4] ={3, 1, 2, 5};
  mergeSort(arr, 0, 3);

  for(int i=0; i<4; i++){
     printf("%i ", arr[i]);
  }
}

合并排序算法不起作用（c++），面临输出没有意义的问题

Merge Sort algorithm Doesn't work(c++), facing problem getting no sense out of output

c++

recursion

merge

mergesort