C++中的Quicksort無限循環問題

我已經廣泛地測試了以下代碼的交換和分區函數，它們似乎是正確的;然而，當我嘗試執行快速排序時，它會陷入無限循環。我假設問題發生在我在分區中返回的值，但我不完全確定它是什麼。C++中的Quicksort無限循環問題

void swap_G(int *begin, int *end) 
{ 
    int temp = *begin; 
    *begin = *end; 
    *end = temp; 
    return; 
} 

int* partition(int* begin, int* end) 
{ 
    if (begin >= end) { 
     return begin; 
    } 

    int pivot = *end; 
    int* temp_Begin = begin, *temp_End = end; 
    temp_End--; 

    while (temp_Begin < temp_End) 
    { 
     while (*temp_Begin < pivot && temp_Begin < temp_End) 
     { 
     temp_Begin++; 
     } 
     while (*temp_End > pivot && temp_End > temp_Begin) 
     { 
     temp_End--; 
     } 
     swap_G(temp_Begin, temp_End); 
    } 
    swap_G(end, temp_Begin); 
    return temp_Begin; 
} 

void quicksort_G(int* begin, int* end) 
{ 
    if (begin >= end) 
    { 
     return; 
    } 
    int* mid = partition(begin, end); 
    quicksort_G(begin, --mid); 
    quicksort_G(mid + 1, end); 
}

來源

2014-03-30 tots_o_tater

讓'begin + 1 == end'，'partition（）'返回什麼值？然後什麼值將遞歸調用到'quicksort_G'？ – CiaPan

使用所有這些指針的任何理由？我看到的一個問題是與中

int* mid = partition(begin, end); 
quicksort_G(begin, --mid)

這是遞減指針中旬。例如：

int* temp = new int(6); 
std::cout << *temp << std::endl; 
std::cout << *(--temp) << std::endl;

你會得到

6 
-33686019

打印內存地址將產生

std::cout << temp << std::endl; 
std::cout << (--temp) << std::endl; 

00BE48B0 
00BE48AC//Decremented by sizeof(int). Garbage data

我會看到，如果我能得到完全擺脫指針。你正在通過那個中期，這將在下一步中被用作結束。但在分區中，結束將被交換。所以當你從第一個遞歸步驟返回時，mid已經搞亂了。

來源

2014-03-31 00:43:31 user3476557

問題可能在您的partition函數中，和肯定與您使用其結果的方式相同。分區函數應對數組項進行重新排序，以使樞軸值落入其最終位置。然後遞歸調用處理之前的這個關鍵點和之後的它，但是這個關鍵點本身並沒有進入深度遞歸層次的處理。這保證了每個遞歸級別數據量的減少，因此遞歸必須停止在某個級別。

來源

2014-04-04 21:31:28 CiaPan

C++中的Quicksort無限循環問題

回答

相關問題