气泡排序递归地

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); 
    } 
} 

有趣的是，这里的每一个递归函数是尾递归，所以一个好的优化编译器应该能够产生非递归码。换句话说，一个好的编译器应该产生几乎相同的代码，就像我们反复写这个代码一样。如果我有时间，我会检查这是否真的发生。 :-)