合併排序實現不起作用

Question

我試圖使用數組裏用C實現歸併排序，這裏是我的代碼：

#include <stdio.h> 
#include <stdlib.h> 

void merge(int s[], int low, int middle, int high) 
{ 
    int i,l=0,r=0; 
    int left[high/2], right[high/2]; 

    for(i = low; i<=middle; i++) left[i-low] = s[i]; 
    for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i]; 

    i = low; 
    while(l <= middle-low || r <= high - middle - 1) 
    { 
     if(left[l] <= right[r]) 
     { 
      s[i++] = left[l]; 
      l++; 
     } 
     else 
     { 
      s[i++] = right[r]; 
      r++; 
     } 
    } 
    while(l <= middle-low) 
    { 
     s[i++] = left[l]; 
     l++; 
    } 
    while(r <= high - middle - 1) 
    { 
     s[i++] = left[r]; 
     r++; 
    } 
} 

void mergesort(int s[], int low, int high) 
{ 
    int i; 
    int middle; 
    if(low < high){ 
     middle = (low + high)/2; 
     mergesort(s, low, middle); 
     mergesort(s, middle+1, high); 
     merge(s, low, middle, high); 
    } 
} 

int main() 
{ 
    int nums[] = {5, 345, 1, 120, 40, 3450}; 
    int size = (sizeof(nums))/(sizeof(int)); 
    int i; 
    for(i = 0; i < size; i++) 
     printf("%d ", nums[i]); 
    printf("\n"); 
    mergesort(nums, 0, size); 
    for(i = 0; i < size; i++) 
     printf("%d ", nums[i]); 
    printf("\n"); 
    return 0; 
} 

輸出：

5 345 1 120 40 3450 
0 1 4 5 40 120 

這是一種接近。有人能指出我的錯誤嗎？謝謝。

Answer 1

你在幾個地方訪問數組越界。您的代碼使用C風格範圍，其中包含下限L和專有上限H。獨佔意味着上限H不是（子）數組中的有效索引。

for (i = L; i < U; i++) ... 

或

i = L; 
while (i < U) ... 

一個大於或 - 等於運營商<=在這樣的循環應該讓你警惕，因爲應suprious添加或減法：在範圍看起來像一個典型的循環1.在某些情況下它們可能是正確的，但它們通常是不穩定的數組索引的後果。

讓我們修改與C風格的範圍你的代碼記：

int left[high/2], right[high/2]; 

的數組的大小是錯誤的。左邊的數組有middle - low個元素，右邊的數組有high - middle個元素。如果數組大小爲high - low是奇數，則右側的元素多於左側。

for(i = low; i<=middle; i++) left[i-low] = s[i]; 

你錯誤地把中間元素放在左邊的數組中。它是正確數組的第一個元素。

for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i]; 

同樣在這裏，加上你訪問s[high]這是一個超出數組。

i = low; 
while(l <= middle-low || r <= high - middle - 1) 

應具備的條件和<沒有-1。更重要的是，這兩個條件都應該是真實的，否則你會進入超出邊界的子陣列;因此運營商應該是'& &`。

if(left[l] <= right[r]) 

該<=是好的，但只有一次。

while(l <= middle-low) 
{ 
    s[i++] = left[l]; 
    l++; 
} 
while(r <= high - middle - 1) 
{ 
    s[i++] = left[r]; 
    r++; 
} 

在這裏，它應該是<了。還請注意，您訪問left的索引r，這可能只是複製和粘貼的錯字。

if(low < high){ 
    middle = (low + high)/2; 
    mergesort(s, low, middle); 
    mergesort(s, middle+1, high); 
    merge(s, low, middle, high); 
} 

這裏，megesort第二個電話應該是middle，不middle + 1。因爲上限是獨佔的而下限不是，所以相鄰的數組共享相同的界限。

這裏有一個排序的作品：

void merge(int s[], int low, int middle, int high) 
{ 
    int i, l = 0, r = 0; 
    int left[middle - low]; 
    int right[high - middle]; 

    for (i = low; i < middle; i++) left[i - low] = s[i]; 
    for (i = middle; i < high; i++) right[i - middle] = s[i]; 

    i = low; 
    while (low + l < middle && middle + r < high) { 
     if (left[l] < right[r]) { 
      s[i++] = left[l]; 
      l++; 
     } else { 
      s[i++] = right[r]; 
      r++; 
     } 
    } 

    while (low + l < middle) { 
     s[i++] = left[l]; 
     l++; 
    } 

    while (middle + r < high) { 
     s[i++] = right[r]; 
     r++; 
    } 
} 

void mergesort(int s[], int low, int high) 
{ 
    int middle; 

    if (low + 1 < high) { 
     middle = (low + high)/2; 
     mergesort(s, low, middle); 
     mergesort(s, middle, high); 
     merge(s, low, middle, high); 
    } 
} 

的代碼能夠進一步提高。左側和右側子陣列的不同索引使維護和測試代碼變得困難。如果您已經瞭解了指針算術，那麼您可以完全通過將array + low和大小作爲新的數組基地進行綁定來完成綁定，因爲EOF在評論中已經提出了建議。

Answer 2

M Oehm在他的回答中提供了原始代碼的解釋和固定示例。

這是一個替代版本，它執行臨時數組的一次分配，並使用一對共遞歸函數來避免數據的複製。我不確定爲什麼經常使用自頂向下合併排序，自底向上合併排序是非遞歸的，速度更快一些，而且更易於理解。

在我的系統上，Intel 2600K 3.4ghz，這個例子可以在大約2秒內對2000萬個32位整數進行排序。 （自底向上合併排序大約需要1.9秒）。

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee); 

void TopDownMergeSort(int a[], size_t n) 
{ 
    int *b; 
    if(n < 2)       // if size < 2 return 
     return; 
    b = malloc(n * sizeof(int));  // one time allocation 
    TopDownSplitMergeAtoA(a, b, 0, n); 
    free(b); 
    return; 
} 

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
size_t rr; 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    rr = (ll + ee)>>1;     // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    MergeRuns(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
size_t rr; 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    rr = (ll + ee)>>1;     // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    MergeRuns(a, b, ll, rr, ee);  // merge a to b 
} 

void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;      // b[]  index 
    size_t l = ll;      // a[] left index 
    size_t r = rr;      // a[] right index 
    while(1){       // merge data 
     if(a[l] <= a[r]){    // if a[l] <= a[r] 
      b[o++] = a[l++];   // copy a[l] 
      if(l < rr)     // if not end of left run 
       continue;    //  continue (back to while) 
      while(r < ee)    // else copy rest of right run 
       b[o++] = a[r++]; 
      break;      //  and return 
     } else {      // else a[l] > a[r] 
      b[o++] = a[r++];   // copy a[r] 
      if(r < ee)     // if not end of right run 
       continue;    //  continue (back to while) 
      while(l < rr)    // else copy rest of left run 
       b[o++] = a[l++]; 
      break;      //  and return 
     } 
    } 
}