遞歸合併Sort C++

Question

我想用C++編寫一個遞歸合併排序程序。問題是，我不知道如何獲得基本情況的想法遞歸地工作。任何人都可以告訴我Merg Function(),Split Function()和MergSort()功能的基本情況。我會感謝你。

void Merg(int A[], int s1, int e1, int s2, int e2) 
{ 
    int B[8]; 
    int i=0; 

    while (A[s1] < A[s2]) 
     B[i] = B[s1]; 
     i++; 
     s1++; 

     if (s1 == e1) 
     { 
     B[i] = A[s2]; 
     i++; 
     s2++; 
     } 

    while (A[s2] < A[s1]) 
     B[i] = B[s2]; 
     i++; 
     s2++; 

     if (s2 == e2) 
     { 
     B[i] = A[s1]; 
     i++; 
     s1++; 
     } 
} 

void Split(int A[], int s, int e) 
{ 
    int mid = (s+e)/2; 

    if (s < e && mid != 0) 
    { 
     Split(A, s, mid); 
     Split(A, mid+1, e); 
    } 
    Merg(A, s, mid, mid+1, e); 
} 

int main() 
{ 
    int A[8] = {10,4,8,12,11,2,7,5}; 

    Split(A, 0, 7); 

    return 0; 
} 

Answer 1

基礎案例是保證被排序的陣列，所以無論是空數組或長度的陣列1.

你的合併函數是不正確的，但至少包含了大部分的正確的想法。所有你需要的是進一步的包裝循環和一些條件來防止你的合併運行超過數組的末尾。分割函數完全關閉，分割不遞歸，在遞歸調用mergeSort內發生進一步分割。

1. 如果長度（A）< 2返回//已排序在下半部L和上半H
2. 分裂甲
3. 合併排序大號
4. 合併排序ħ
5. 合併分類L和H
6. 做