java 归并排序递归
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32445391/
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
Merge Sort Recursion
提问by HelenWang
This is a code from Introduction to Java Programming about Merge Sort. This method uses a recursion implementation.
这是 Java 编程简介中关于 Merge Sort 的代码。此方法使用递归实现。
public class MergeSort {
2 /** The method for sorting the numbers */
3 public static void mergeSort(int[] list) {
4 if (list.length > 1) {
5 // Merge sort the first half
6 int[] firstHalf = new int[list.length / 2];
7 System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
8 mergeSort(firstHalf);
9
10 // Merge sort the second half
11 int secondHalfLength = list.length - list.length / 2;
12 int[] secondHalf = new int[secondHalfLength];
13 System.arraycopy(list, list.length / 2,
14 secondHalf, 0, secondHalfLength);
15 mergeSort(secondHalf);
16
17 // Merge firstHalf with secondHalf into list
18 merge(firstHalf, secondHalf, list);
19 }
20 }
My question:is in Line 8 calls the recursion method back to "mergeSort"? If running from the beginning of the method, the "firstHalf" array will be created again and the length will be half short. I think the "firstHalf" can not created again and the length should not be changed if an array is defined already.
我的问题：是否在第 8 行中将递归方法调用回“mergeSort”？如果从方法的开头运行，将再次创建“firstHalf”数组，长度将缩短一半。我认为“firstHalf”不能再次创建，如果已经定义了数组，则不应更改长度。
Here is the whole code link: Merge Sort Java.
这是整个代码链接：Merge Sort Java。
回答by JumpMan
This is beginner's way of thinking. Yes, exactly I thought the same when I encountered this before. I couldn't believe that the same array size can change dynamically. Understand this, in the below code, array l and array rare created with different sizes for every recursive call. Don't confuse on this.
这是初学者的思维方式。是的，我之前遇到这个的时候也是这么想的。我不敢相信相同的数组大小可以动态变化。理解这一点，在下面的代码中，array l and array r为every recursive call. 不要混淆这一点。
Yes, this is never possible that the same array size changes dynamically for a beginner like you and me. But, there is an exception, well, there are exceptions. We will see them very often as we move forward.
是的，对于像你我这样的初学者来说，相同的数组大小动态变化是不可能的。但是，有一个例外，嗯，有例外。在我们前进的过程中，我们会经常看到它们。
Its recursion, in recursion things change dynamically and all this changes are stored in a call stack.
它的递归，在递归中，事物是动态变化的，所有这些变化都存储在调用堆栈中。
Its confusing but its really interesting if you ponder over it. Its profound. Merge sort can be implemented in quite different ways, but the underlying concept of recursion is same. Don't get confused here, Its better you follow another way to do it, video:
它令人困惑，但如果您仔细考虑一下，它真的很有趣。其深刻。归并排序可以以完全不同的方式实现，但递归的基本概念是相同的。不要在这里混淆，你最好按照另一种方式来做，视频：
Merge sort first takes a list or an array. Lets imagine the
合并排序首先需要一个列表或一个数组。让我们想象一下
a.length; #lenght of an array is 8
Now the end goal is to split the array recursively, till it reaches to a point where there are no-elements (only-one). And a single element is always sorted.
现在的最终目标是递归地拆分数组，直到它达到没有元素（只有一个）的点。和一个single element is always sorted。
See the base case in the below code:
请参阅以下代码中的基本情况：
if(a.length<2) /*Remember this is the base case*/
{
return;
}
Once it reaches to single element, sort and merge them back. This way you get a complete sorted array which is easy to merge. The only reason we are doing all this non-sense is to get a better run-time algorithm which is O(nlogn).
一旦到达单个元素，将它们排序并合并回来。这样你就可以得到一个完整的排序数组，它很容易合并。我们做这些毫无意义的事情的唯一原因是为了获得一个更好的运行时算法，即O(nlogn)。
Because, all the other sorting algos (insertion, bubble, and selection) will take O(n2), which is alot, too much indeed. So, humanity must figure out the better solution. Its a need for humanity, very important. I know its annoying, I had gone through this non-sense.
因为，所有其他排序算法 ( insertion, bubble, and selection) 都需要O(n2)，这确实太多了。因此，人类必须找出更好的解决方案。它是人类的需要，非常重要。我知道这很烦人，我经历过这种胡说八道。
Please do some research on recursion before you attempt on this. Understand recursion clearly. Keep all this away. Take a simple recursion example and start working on it. Take a factorial example. Its a bad example but its easy to understand.
在尝试之前，请对递归进行一些研究。清楚地理解递归。远离这一切。举一个简单的递归示例并开始研究它。举一个阶乘的例子。这是一个不好的例子，但很容易理解。
Top-down MergeSort
自上而下的归并排序
See my code, its nice and easy. Again, both are not easy to understand on your first attempt. You must get in touch with recursion before you attempt to understand these things. All the very best.
看我的代码，它很好很简单。同样，在您第一次尝试时，两者都不容易理解。在尝试理解这些事情之前，您必须先了解递归。一切都非常好。
public class MergeSort
{
private int low;
private int high;
private int mid;
public static int[] a;
public MergeSort(int x)
{
a = new int[x];
a[0]=19;
a[1]=10;
a[2]=0;
a[3]=220;
a[4]=80;
a[5]=2000;
a[6]=56001;
a[7]=2;
}
public void division(int[] a)
{
low=0;
int p;
high = a.length;
mid = (high+low)/2;
if(a.length<2) /*Remember this is the base case*/
{
return;
}
else
{
int[] l = new int[mid];
int[] r = new int[high-mid];
/*copying elements from a into l and r*/
for(p=0;p<mid;p++)
l[p]=a[p];
for(int q=0;q<high-mid;q++, p++)
r[q]=a[p];
/*first recursive call starts from here*/
division(l);
division(r);
sortMerge(a, l, r);
}
}
public void sortMerge(int[] a, int[] l, int[] r)
{
int i=0, j=0, k=0;
/*sorting and then merging recursively*/
while(i<l.length && j<r.length)
{
if(l[i]<r[j])
{
a[k] = l[i]; /*copying sorted elements into a*/
i++;
k++;
}
else
{
a[k] = r[j];
j++;
k++;
}
}
/*copying remaining elements into a*/
while(i<l.length)
{
a[k] = l[i];
i++;
k++;
}
while(j<r.length)
{
a[k] = r[j];
j++;
k++;
}
}
/*method display elements in an array*/
public void display()
{
for(int newIndex=0;newIndex<a.length;newIndex++)
{
System.out.println(a[newIndex]);
}
}
public static void main(String[] args)
{
MergeSort obj = new MergeSort(8);
obj.division(a);
obj.display();
}
}
回答by user3402754
Here is an alternative implementation of merge sort, this is bottom-up MergeSort
这是合并排序的另一种实现，这是 bottom-up MergeSort
public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {
for (int k = f; k <= l; k++) {
aux[k] = a[k];
}
int i = f, j = m+1;
for (int k = f; k <= l; k++) {
if(i>m) a[k]=aux[j++];
else if (j>l) a[k]=aux[i++];
else if(aux[j] > aux[i]) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
public static void sort(int[]a,int[] aux, int f, int l) {
if (l<=f) return;
int m = f + (l-f)/2;
sort(a, aux, f, m);
sort(a, aux, m+1, l);
merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
int[] aux = new int[a.length];
sort(a, aux, 0, a.length-1);
return a;
}
}
回答by Stefan Bollmann
As it was pointed out by Emz: This is due to scope reasons. A local variable is a new object. [
正如 Emz 指出的那样：这是由于范围原因。局部变量是一个新对象。[
Local variables are declared by local variable declaration statements (§14.4).
Whenever the flow of control enters a block (§14.2) or for statement (§14.14), a new variable is created for each local variable declared in a local variable declaration statement immediately contained within that block or for statement.
A local variable declaration statement may contain an expression which initializes the variable. The local variable with an initializing expression is not initialized, however, until the local variable declaration statement that declares it is executed. (The rules of definite assignment (§16) prevent the value of a local variable from being used before it has been initialized or otherwise assigned a value.) The local variable effectively ceases to exist when the execution of the block or for statement is complete.]1
局部变量由局部变量声明语句（第 14.4 节）声明。
每当控制流进入块（第 14.2 节）或 for 语句（第 14.14 节）时，都会为在该块或 for 语句中立即包含的局部变量声明语句中声明的每个局部变量创建一个新变量。
局部变量声明语句可能包含初始化变量的表达式。然而，在执行声明它的局部变量声明语句之前，不会初始化带有初始化表达式的局部变量。（确定赋值规则（第 16 节）防止局部变量的值在它被初始化或以其他方式赋值之前被使用。）当块或 for 语句的执行完成时，局部变量实际上不复存在.] 1
