合併算法

Question

這裏是合併了歸併的實現，在Java的作品：

void merge(int[] numbers, int low, int mid, int high) { 
    int helper[] = new int[numbers.length]; 
    for (int i = low; i <= high; i++) { 
     helper[i] = numbers[i]; 
    } 

    int lowone = low; 
    int lowtwo = mid + 1; 
    int count = low; 

    while (lowone <= mid || lowtwo <= high) { 
     if (lowone <= mid && lowtwo <= high) { 
      if (helper[lowone] <= helper[lowtwo]) { 
       numbers[count] = helper[lowone]; 
       lowone++; 
      } else { 
       numbers[count] = helper[lowtwo]; 
       lowtwo++; 
      } 
     } 
     else if (lowone <= mid) { 
       numbers[count] = helper[lowone]; 
       lowone++; 
      } 
     else { 
       numbers[count] = helper[lowtwo]; 
       lowtwo++; 

     } 
     count++; 
    } 
} 
//msort algorithm in case it's relevant 
void msort(int[] arr, int low, int high) { 
    if (low < high) { 
     int mid = (low + high)/2; 

     msort(arr, low, mid); 
     msort(arr, mid + 1, high); 

     merge(arr, low, mid, high); 
    } 
} 

在我第一次嘗試合併，我想有數組的後半部分包含中點指數，而不是具有它在上半場。這裏是relavent代碼（注意，是從上面只有4個變化）：

int lowtwo = mid; 

    while (lowone < mid || lowtwo <= high) { 
     if (lowone < mid && lowtwo <= high) { 
      if (helper[lowone] <= helper[lowtwo]) { 
       numbers[count] = helper[lowone]; 
       lowone++; 
      } else { 
       numbers[count] = helper[lowtwo]; 
       lowtwo++; 
      } 
     } 
     else if (lowone < mid) { 
       numbers[count] = helper[lowone]; 
       lowone++; 
     } 
     else { 
       numbers[count] = helper[lowtwo]; 
       lowtwo++; 
     } 

與msort（以上）使用修改後的版本不正確列表進行排序。也許這很明顯，但我似乎無法弄清楚爲什麼它不起作用。

Answer 1

問題出現是因爲您在合併中更改了mid的含義。查看它的最簡單方法就是一個例子。假設我們有一個索引數組：

[0 1 2 3 4] 

調用msort時，您將0傳遞給低，4傳給高。這意味着中期被計算爲2。所以，你現在有分爲左右（未在內存中，只是邏輯上）數組：

[0 1 2] [3 4] 

現在，當合並被稱爲它在2過去了中旬，這是最後一個在陣列然而指數，在你修改後的代碼你把作爲中期開始索引數組2.這使得兩個數組看起來像：

[0 1] [2 3 4] 

這是不同的一切又如何對待它。這個地方倒下的一個例子是，如果你兩個數組（排序後）看起來像（數字現在是值，而不是指數）：

[8 12 14] [7 11] 

然而，在你中旬解釋，陣列是：

[8 12] [14 7 11] 

哪些不再排序。因此，你的合併功能將無法正常工作。

Answer 2

這是因爲您已經在第一個子數組中的中點（msort(...)）中排序了第二個子數組中的中點（merge(...)）中的兩個子列表。

以最簡單的例子

[2,1]

被分裂像這樣的（因爲中間==（（0 + 1）/ 2）== 0）

[2]和[1]

其中msort平凡分類成

[2]和[1]

但N，通過合併將在中期的第二個列表，你實際上合併：

[]和[2,1]

這顯然導致[2,1]，這是不對的！

中點位置在兩個子陣列的分裂和合並中必須一致。