0

我编写了 2 个冒泡排序算法。一种是没有递归的，另一种是有递归的。我有兴趣知道这两者中哪一个更有效，并解释为什么。

递归冒泡排序：

private static int list[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

public int[] recursiveBubble(int[] args, int startIndex, int endIndex) {
    if(startIndex > endIndex){
        System.out.println("Recursive bubblesort:");
        System.out.println(Arrays.toString(args));
        return args;
    }

    if (startIndex == endIndex - 1) {
        recursiveBubble(args, 0, endIndex - 1);
    } else if (args[startIndex] > args[startIndex+1]) {
        int currentNumber = args[startIndex];
        args[startIndex] = args[startIndex + 1];
        args[startIndex + 1] = currentNumber;

        recursiveBubble(args, startIndex + 1, endIndex);
    } else  {
        recursiveBubble(args, startIndex + 1, endIndex);
    } 
    return args;
}

BubbleSort 使用循环：

 public int[] bubblesort(int[] args) {
    System.out.println("Normal BubbleSort:");
    for (int j = 0; j < args.length; j++) {
        for (int i = 0; i < args.length; i++) {
            int currentNumber = args[i];
            if (i + 1 < args.length) {
                if (currentNumber > args[i + 1]) {
                    args[i] = args[i + 1];
                    args[i + 1] = currentNumber;
                }
            }
        }
    }
    System.out.println(Arrays.toString(args));
    return args;
}
4

2 回答 2

3

我不确定您的意思是哪个更好，但根据算法的工作方式，冒泡排序本质上必须具有最佳和最差情况的性能时间。最佳情况 O(n) 最坏情况 O(n^2) 请参阅http://en.wikipedia.org/wiki/Bubble_sort。迭代与递归不应该有太大的区别。我想递归会占用更多的堆栈内存。递归往往比迭代更难编写和跟踪。由于如果两者都是实际的冒泡排序实现，则没有时间优势，我会坚持迭代。

于 2013-10-02T15:33:01.130 回答
-1

在上面的示例中，您更少将循环替换为递归。在 java 中，递归版本可能不好，因为它可能导致基于长数组长度的 stackoverflow 错误。复杂性方面我看不出有什么区别。如果您比较 JVM 的内存管理，那么递归版本将比您的正常循环占用更多的内存空间。如果您增加变量的长度，您可能会注意到这种差异，或者您可能会遇到基于内存代分配大小的 stackoverflow 异常。

于 2013-10-02T16:05:16.647 回答