我的兩個排序數組的合併有什麼問題？

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--; 
      } 

     } 
    }