Java 递归冒泡排序与普通冒泡排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19140628/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive BubbleSort vs normal BubbleSort
提问by JP24
I have coded 2 bubblesort algorithms. One is without recursion, the other is with recursion. I am interested on knowing which of these two are more efficient and with and explain why.
我编写了 2 个冒泡排序算法。一个是没有递归的，另一个是有递归的。我很想知道这两个中哪一个更有效，并解释原因。
Recursive bubbleSort:
递归冒泡排序：
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 using loops:
使用循环的 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;
}
采纳答案by ford prefect
I am not sure what you mean by which is better but bubble sort must inherently have a best and worst case performance time by nature of the way the algorithm works. Best case O(n) worst case O(n^2) see http://en.wikipedia.org/wiki/Bubble_sort. Iteration vs. recursion shouldn't make too much of a difference. I suppose recursion will take up more stack memory. Recursion tends to be harder to write and trace than iteration. Since there is no time benefit if both are actual bubble sort implementations I would stick to iteration.
我不确定你的意思是哪个更好，但根据算法的工作方式，冒泡排序本质上必须具有最佳和最坏情况的性能时间。最佳情况 O(n) 最坏情况 O(n^2) 参见http://en.wikipedia.org/wiki/Bubble_sort。迭代与递归不应该有太大区别。我想递归会占用更多的堆栈内存。递归比迭代更难编写和跟踪。由于如果两者都是实际的冒泡排序实现，则没有时间优势，因此我会坚持迭代。
回答by Mohammad Adnan
In the above example you are more less replacing loops to recursion. In java recursive version is possibly not good because it can lead a stackoverflow error based on long array length. complexity wise I don't see any difference. IF you compare memory management of JVM then recursive version is going to take more space in memory than your normal loop one. if you increase length of your variable you may notice that difference or you may encounter an stackoverflow exception based on allocated size for your memory generations.
在上面的例子中，你更少地将循环替换为递归。在 Java 中，递归版本可能不好，因为它会导致基于长数组长度的计算器溢出错误。复杂性明智我没有看到任何区别。如果您比较 JVM 的内存管理，那么递归版本将比普通循环占用更多的内存空间。如果您增加变量的长度，您可能会注意到这种差异，或者您可能会遇到基于内存代分配大小的计算器溢出异常。
