我的合併排序沒有給出正確的排序數組，任何人都可以解釋嗎？

-1

我掙扎了好幾個小時來理解和實現這個算法，我很確定，我按照標準算法做了所有事情，但仍然沒有工作。我下面一個名爲書我的合併排序沒有給出正確的排序數組，任何人都可以解釋嗎？

#include<iostream> 
using namespace std; 

//function to divide the array until it has only one element 
void merge_sort(int[], int, int); 

// function to merge two sorted arrays 
void merge(int[], int, int, int); 

// global array - to write the final sorted array in this 
int na[100]; 

void main() { 
    int a[50]; //input array 
    cout << "Enter an unsorted array of 10 elements" << endl; 
    for (int i = 0; i < 10; i++) { 
     cin >> a[i]; 
    } 
    merge_sort(a, 0, 9); // calling merge_sort 
    for (int i = 0; i < 10; i++) { 
     //print final array 
     cout << na[i] << endl; 
    } 
} 

void merge_sort(int a[], int p, int r) { 
    // p is 0 , r is final bound 
    if (p < r) { 
     int q; 
     q = (p + r)/2; //finding middle element 
     merge_sort(a, p, q); 
     merge_sort(a, q + 1, r); 
     merge(a, p, q, r); 
    } 

} 

// for two sorted sub-array from p to q and from q+1 to r, this function 
// will compare first element of each sub-array and will place the smaller 
// one in final array until every element is sub-array is in final sorted 
//array 
void merge(int a[], int p, int q, int r) { 
    int n1 = q - p + 1; 
    int n2 = r - q; 
    int l[50]; 
    int ri[50]; 
    for (int i = 0; i < n1; i++) { 
     l[i] = a[p + i ]; 
    } 
    l[n1] = 99999; 

    for (int j = 0; j < n1; j++) { 
     ri[j] = a[q + j + 1]; 
    } 
    ri[n2] = 99999; 

    int i = 0; 
    int j = 0; 
    for (int k = p; k <= r; k++) { 
     if (l[i] <= ri[j]) { 
      na[k] = l[i]; 
      i = i + 1; 
     } 
     else { 
      na[k] = ri[j]; 
      j = j + 1; 
     } 
    } 

}

來源

2017-07-13 Vishal Tewatia

你應該更新你的資源，'void main（）'是不可接受的。 –

您可以檢查代碼和變量的行爲，逐行執行調試器。 – user0042

1）'j < n1;' -->'j BLUEPIXY

您正在使用a值合併「的介紹托馬斯達cormen到算法」，但你把分揀子陣中na。如果子數組排序，那麼merge操作只會給你一個排序數組。正如BLUEPIXY所建議的那樣，您需要使用一個容器來存儲排序後的子陣列和合並排序後的子陣列：無論您使用的是a還是na都不重要，但是因爲您已經擁有了a將是更好的選擇。

來源

2017-07-13 18:09:24 Patrick87

嘗試閱讀在StackOverflow上提出問題的指導原則。
在歸併，要合併無序陣列，而不是那些排序（void merge_sort(int a[], int p, int r)：因爲你是合併a[]，你應該排序a[]而不是na[]）。

否則合併的na[]段和把它複製到a[]中的每個函數調用merge_sort（:);

來源

2017-07-13 18:17:04 Deceptor

我的合併排序沒有給出正確的排序數組，任何人都可以解釋嗎？

回答

相關問題