我的两个排序数组的合并有什么问题？

Question

void sort(int a[], int b[], int m, int n) 
    { 
     int e = m + n; 
     while(m >=0 && n >=0) 
     { 
      if(a[m] > b[n]) 
      { 
       a[e] = a[m]; 
       m--; 
       e--; 
      } 
      else if(a[e] < b[n]) 
      { 
       a[e] = b[n]; 
       n--; 
       e--; 
      } 
      else 
      { 
       a[e] = b[n]; 
       e--; 
       n--; 
       m--; 
      } 
     } 
    } 

public static void main(String[] args) { 
     SortSorted obj = new SortSorted(); 
     int a[] = new int [6]; 
     int b[] = new int [3]; 
     a[0] = 1; 
     a[1] = 2; 
     a[2] = 3; 
     b[0] = 2; 
     b[1] = 7; 
     b[2] = 8; 
     obj.sort(a,b, 2, 2); 
    } 

我得到的输出为1 2 3 7 8 0而不是1 2 2 3 7 8有和没有添加3rd else条件。

Answer 1

您开始e太低，应该是m + n + 1。

想一想，对于两个三元阵列，m和n都是两个。这意味着你将以四分之一开始m + n，而六分的结果应该从五分开始。

这是一个相对简单的错误。

您也可以修复其他当它们相等时丢失值的问题，只需忽略相等性。如果它大于或等于，则选择a，否则选择b。

而你的循环连续逻辑是错误的，你会看到如果你用尽a第一（使用a = {2, 2, 3}和b = {1, 7, 8}来看看我的意思）。如果a和b都剩下元素，则只能继续。你应该继续，而要么他们有元素。

你可以通过保持原样，但添加两个其他循环（其中只有一个实际上会做任何事情）来消除另一个列表。

作为支撑，我提供了下面的C代码（因为我与比Java快，但排序过程本身应该是差不多相同）：

#include <stdio.h> 

void sort (int a[], int b[], int m, int n) { 
    // Start at correct offset for target array. 

    int e = m + n + 1; 

    // Until one list empty, choose the correct value. 

    while (m >= 0 && n >= 0) 
     if (a[m] >= b[n]) 
      a[e--] = a[m--]; 
     else 
      a[e--] = b[n--]; 

    // If b was empty, just transfer a. 

    while (m >= 0) 
     a[e--] = a[m--]; 

    // If a was empty, just transfer b. 

    while (n >= 0) 
     a[e--] = b[n--]; 
} 

和一些测试代码：

int main(void) { 
    int a[6] = {2,2,3}; 
    int b[] = {1,7,8}; 
    sort (a, b, 2, 2); 
    printf ("%d %d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4], a[5]); 
    return 0; 
} 

的这个输出是：

1 2 2 3 7 8 

如预期。

---

以及等效的Java代码：

class Test { 
    static void sort (int a[], int b[], int m, int n) { 
     // Start at correct offset for target array. 

     int e = m + n + 1; 

     // Until one list empty, choose the correct value. 

     while (m >= 0 && n >= 0) 
      if (a[m] >= b[n]) 
       a[e--] = a[m--]; 
      else 
       a[e--] = b[n--]; 

     // If b was empty, just transfer a. 

     while (m >= 0) 
      a[e--] = a[m--]; 

     // If a was empty, just transfer b. 

     while (n >= 0) 
      a[e--] = b[n--]; 
    } 

其测试套件一起：

static public void main(String[] args) { 
     int a[] = new int[6]; 
     a[0] = 2; a[1] = 2; a[2] = 3; 
     int b[] = new int[3]; 
     b[0] = 1; b[1] = 7; b[2] = 8; 
     sort (a, b, 2, 2); 
     for (int i = 0; i < 6; i++) 
      System.out.println (a[i]); 
    } 
} 

---

事实上，因为你反正写a，你可以实际上忽略了中间循环（while (m >= 0)之一）。那是因为在这种情况下，你只是简单地将元素转移到自己身上。

，因为它变得很重要，如果你正在写的数组不是就地但如果你想为你的特殊情况下，你可以将其删除，我会离开进去。

Answer 2

这是你的其他陈述。 a和b中的元素是相同的，所以您应该插入两者，顺序无关紧要。相反，你只能从b中插入值。或者你可以扔第二个条件，并如下更改：

void sort(int a[], int b[], int m, int n) 
    { 
     int e = m + n + 1; 
     while(m >=0 && n >=0) 
     { 
      if(a[m] > b[n]) 
      { 
       a[e] = a[m]; 
       m--; 
       e--; 
      } 
      else 
      { 
       a[e] = b[n]; 
       n--; 
       e--; 
      } 

     } 
    }