递归冒泡排序

发布于 2024-10-07 16:23:57 字数 175 浏览 12 评论 0原文

我搜索过谷歌,但找不到任何相关内容。我一直在寻找各种类型的排序(正如您在我之前的问题中看到的那样),我想知道是否有人知道递归冒泡排序代码。对我来说,这个想法听起来很荒谬,但我想为此做好准备,并且我很好奇这是否可以做到。我确信可以,因为我的一位教授过去曾这样问过他的学生。我认为他不会重复问题,但我很好奇,想知道是否有递归冒泡排序的代码。

I have searched Google and I cannot find anything for this. I was looking for various types of sorts (as you can see in a previous question of mine) and I was wondering if anyone knew of a recursive bubble sort code. To me, the idea sounds ridiculous, but I want to be prepared for things and I'm curious as to whether or not this can be done. I'm sure it can, as a professor of mine has asked this of his students in the past. I don't think he'll repeat questions, but I became curious and wanted to know if there was code for a bubble sort recursively.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

若相惜即相离 2024-10-14 16:23:57

这当然是可能的,因为任何迭代算法都可以转换为递归算法,反之亦然。

这是我们可以做到这一点的一种方法。为简单起见,我使用 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);
    }
}

有趣的是,这里的每个递归函数都是尾递归的,因此一个好的优化编译器应该能够生成非递归代码。换句话说,一个好的编译器应该生成与我们迭代编写的代码几乎相同的代码。如果我有时间,我会检查这是否真的发生。 :-)

It's certainly possible to do this, since any iterative algorithm can be converted to a recursive one and vice-versa.

Here's one way that we can do this. For simplicity, I'm using C++ and assuming the inputs are all integers.

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

Interestingly, every recursive function here is tail-recursive, so a good optimizing compiler should be able to generate non-recursive code. In other words, a good compiler should generate pretty much the same code as if we'd written this iteratively. If I get the time, I'll check out whether this actually happens. :-)

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文