C++：從零開始實現合併排序

我試圖測試我的自我，並希望編寫mergesort，而不實際在線查找任何代碼，並在特定時間段內執行此操作。我被困在這一點上，我不能簡單地理解我在做什麼錯誤，因爲合併排序，就像我記得的那樣，是將字符串分成只有1個字符的字符串，然後再合併到一起。我在下面寫的代碼嘗試來做確切的事情。我想知道我是否得到了概念錯誤，或者只是我的執行？C++：從零開始實現合併排序

string merge(string str1, string str2) { 
    string final = ""; 
    int i = 0, j = 0; 
    bool fromStr1 = false; 

    while(true) { 
    if(str1[i] < str2[j]) { 
     final += str1[i]; 
     i++; 
     if(i == str1.size()) { 
     break; 
     } 
    } 
    else { 
     final += str2[j]; 
     j++; 
     if(j == str2.size()) { 
     break; 
     fromStr1 = true; 
     } 
    } 
    } 

    if(fromStr1) { 
    for(int t = i; t < str1.size(); t++) { 
     final += str1[t]; 
    } 
    } 
    else { 
    for(int t = j; t < str2.size(); t++) { 
     final += str2[t]; 
    } 
    } 

    return final; 
} 

string mergeSort(string str1, int start, int end) { 
    if(end - start == 1) 
    return str1; 
    else { 
    int pivot = (end - start)/2; 
    string newStr1 = mergeSort(str1, start, pivot); 
    string newStr2 = mergeSort(str1, pivot + 1, end); 
    return merge(newStr1, newStr2); 
    } 
}

來源

2013-04-17 Ali

聽起來像是你有這個概念對的，儘管這是很常見的，停止分裂的事情，當你到少數項目，並使用（例如）插入排序來處理少量項目，然後合併這些運行。 –

嗯，一件事你只有一個字符串....你在分裂階段永遠不會分裂它。 – Yakk

注意的變化：

#include <iostream> 
#include <string> 

using namespace std; 

string merge(string str1, string str2) { 
    string final = ""; 
    int i = 0, j = 0; 
    bool fromStr1 = false; 

    while (true) { 
    if (i >= (int)str1.size()) { 
     break; 
    } 
    if (j >= (int)str2.size()) { 
     fromStr1 = true; // changed the order of this with break! 
     break; 
    } 

    if (str1[i] < str2[j]) { 
     final += str1[i]; 
     i++; 
    } 
    else { 
     final += str2[j]; 
     j++; 
    } 
    } 

    if (fromStr1) { 
    for (int t = i; t < (int)str1.size(); t++) { 
     final += str1[t]; 
    } 
    } 
    else { 
    for(int t = j; t < (int)str2.size(); t++) { 
     final += str2[t]; 
    } 
    } 

    return final; 
} 

string mergeSort(string str1) { 
    int len = str1.size(); 
    if (len <= 1) 
    return str1; 
    else { 
    string newStr1 = mergeSort(str1.substr(0, len/2)); 
    string newStr2 = mergeSort(str1.substr(len/2, len - len/2)); 
    return merge(newStr1, newStr2); 
    } 
} 

int main() 
{ 
    cout << '"' << mergeSort("") << '"' << endl; 
    cout << '"' << mergeSort("a") << '"' << endl; 
    cout << '"' << mergeSort("ba") << '"' << endl; 
    cout << '"' << mergeSort("132") << '"' << endl; 
    cout << '"' << mergeSort("4321") << '"' << endl; 
    cout << '"' << mergeSort("54321") << '"' << endl; 
    return 0; 
}

輸出（ideone）：

"" 
"a" 
"ab" 
"123" 
"1234" 
"12345"

來源

2013-04-18 06:21:38

非常感謝您提供完美的答案，並感謝您以我想要的方式解決問題。 – Ali

自從我使用C++以來，這已經過時了，但是不立即退出循環？因爲fromStr1 = true;在這種情況下永遠不會達到。

來源

2013-04-17 23:09:30

這看起來不正確：

int pivot = (end - start)/2; 
string newStr1 = mergeSort(str1, start, pivot); 
string newStr2 = mergeSort(str1, pivot + 1, end);

你不是說pivot=(end+start)/2？否則mergeSort(str1, start, start+pivot)和mergeSort(str1, start+pivot+1, end)？

編輯：

而且你merge不與空字符串很好應付。在連接到mergeSort之前，您應該已經測試過該功能。

來源

2013-04-17 23:26:41 Beta

C++：從零開始實現合併排序

回答

相關問題