合併排序算法建議

Question

我做了一個程序，使用合併排序算法對列表進行排序。

問題是，我認爲它應該工作，但它不工作，合併函數返回作爲參數發送的數組。你能看看我寫的代碼，告訴我什麼是錯的，以及如何改進它。

感謝

void merge_sort(int *niz, int low, int medium, int high) { 

int *niz2 = new int[high-low]; 

int bottom = low; 
int top = medium + 1; 

for (int f1=low; f1<high-low; f1++) { 
    if (low > medium) { 
     niz2[f1] = niz[top++]; 
    } 
    else if (top > high) { 
     niz2[f1] = niz[bottom++]; 
    } 
    else if (niz[bottom] < niz[top]) { 
     niz2[f1] = niz[bottom++]; 
    } 
    else { 
     niz2[f1] = niz[top++]; 
    } 
} 
niz = niz2; 
} 

void merge(int *niz, int low, int high) { 
if (low < high) { 
    int medium = (high+low)/2; 
    merge(niz, low, medium); 
    merge(niz, medium+1, high); 
    merge_sort(niz, low, medium, high);   
} 
} 

程序的輸出：

3 5 2 3 4 9 5 2 7 10 
3 5 2 3 4 9 5 2 7 10 

Answer 1

您是按值傳遞的指針，因此該值分配給niz內部功能在調用函數可見。

您的簽名應該是 void merge(int niz[], int low, int medium, int high)和 void merge_sort(int niz[], int low, int high)。

在merge你有一個名爲merge_sort，在底部，那麼你應該將內容複製回從niz2到niz，而不是niz = niz2。

* 編輯 - * 你也已經得到了merge功能失常（你有一個名爲merge_sort）。如果說你用low = 100，medium = 120,high = 140調用函數。

然後for (int f1=low; f1<high-low; f1++)永遠不會循環。

它應該是for (int f1=0; f1<high-low; f1++)。上述錯誤的另一個後果是SIGSGV，因爲您將訪問niz2越界（對於給定示例）。

Answer 2

我想有很多錯誤，在此代碼，但最大的一個是

niz = niz2; 

在這裏，您正試圖將niz2陣列複製回niz，但它沒有做到這一點，它只是拷貝指針。

Answer 3

我看到您試圖通過niz = niz2; 將niz2的內容分配到niz。這是不正確的，因爲niz是一個按值傳遞的指針，而niz2是一個指向數組的本地指針。

如果要複製niz2到niz您可能需要像for (int i = low; i < high; i++) niz[i] = niz2[i]一個循環，使用API​​函數類似的memcpy覆蓋輸入陣列，或者如果你想在int* niz指針使用新創建的niz2陣列重定向，那麼你需要通過輸入作爲指針指針，然後直接修改它，例如merge_sort(int** niz, int low...)並通過merge_sort(&niz, 0, 20);調用它。這並不是說，如果你做的修改輸入指針指向一個新的數組，你應該刪除舊的第一，如delete [] *niz; *niz = niz2;

聲明niz = niz2;複製地址指向niz2了在參數列表中的臨時niz指針。當您將指針傳遞給接收int*（如foo(int* nPtr);）的函數時，您發送的指針將被複制到臨時變量/指針nPtr中。使用foo(int** nPtr);告訴它它正在處理'int指針的地址'，而不僅僅是'int的地址'。在這種情況下，您可以通過*nPtr = &tmpInt或*nPtr = tmpPtr等語句重定向nPtr。要從源頭獲得實際的int或數據，您可以使用tmpInt = **nPtr。