氣泡排序遞歸地

Question

我已經搜索谷歌，我找不到任何這個。我正在尋找各種類型的（正如你可以在我以前的問題中看到的那樣），我想知道是否有人知道遞歸冒泡排序代碼。對我來說，這個想法聽起來很荒謬，但我想爲事情做好準備，我很好奇這件事是否可以完成。我確信它可以，正如我的教授過去曾問過他的學生。我不認爲他會重複提問，但我很好奇，想知道是否有遞歸的泡泡排序代碼。

Answer 1

這樣做肯定是可行的，因爲任何迭代算法都可以轉換爲遞歸算法，反之亦然。

下面是我們可以做到這一點的一種方法。爲了簡單起見，我使用C++並假設輸入都是整數。

void bubbleSort(std::vector<int>& list) { 
    /* Make one pass of swapping elements. If anything was swapped, 
    * repeat this process. 
    */ 
    if (swapPass(list)) { 
     bubbleSort(list); 
    } 
} 

/* Does a pass over the array, swapping adjacent elements if they're 
* out of place. Returns true if anything was swapped and false 
* otherwise. 
*/ 
bool swapPass(std::vector<int>& list) { 
    return recSwapPass(list, 0, false); 
} 

/* Does a swap pass starting from index given information about 
* whether a swap was made on the pass so far. Returns true if across 
* the entire pass a swap was made and false otherwise. 
*/ 
bool recSwapPass(std::vector<int>& list, unsigned index, 
       bool wasSwapped) { 
    /* Base case: If we're at the end of the array, then there's 
    * nothing to do and we didn't swap anything. 
    */ 
    if (index + 1 >= list.size()) return wasSwapped; 

    /* Compare the current element against the next one and see if 
    * they need to swap. 
    */ 
    if (list[index] > list[index + 1]) { 
     std::swap(list[index], list[index + 1]); 
     return recSwapPass(list, index + 1, true); 
    } else { 
     return recSwapPass(list, index + 1, wasSwapped); 
    } 
} 

有趣的是，這裏的每一個遞歸函數是尾遞歸，所以一個好的優化編譯器應該能夠產生非遞歸碼。換句話說，一個好的編譯器應該產生幾乎相同的代碼，就像我們反覆寫這個代碼一樣。如果我有時間，我會檢查這是否真的發生。 :-)