合并排序递归

Question

这是 Java 合并排序编程简介中的一段代码。此方法使用递归实现。

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    }

我的问题：是在第8行调用递归方法返回"mergeSort"？如果从方法的开头运行，会重新创建"firstHalf"数组，长度减半。我认为 "firstHalf" 不能再次创建，如果已经定义了数组，则不应更改长度。

这是完整的代码link：Merge Sort Java。

Answer 1

正如 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

Answer 2

这是初学者的思路。是的，我之前遇到这个的时候也是这么想的。我无法相信相同的数组大小可以动态变化。理解这一点，在下面的代码中，array l and array r 是为 every recursive call 创建的，具有不同的大小。不要混淆这一点。

是的，对于像你我这样的初学者来说，动态改变相同的数组大小是不可能的。但是，有一个例外，嗯，有例外。在我们前进的过程中，我们会经常看到他们。

Its recursion, in recursion things change dynamically and all this changes are stored in a call stack.

虽然很迷惑，但细细想来，还是很有趣的。它的深刻。归并排序可以用完全不同的方式实现，但递归的基本概念是相同的。不要在这里混淆，你最好按照另一种方式去做，video:

归并排序首先取一个列表或数组。让我们想象一下

a.length; #lenght of an array is 8

现在的最终目标是递归拆分数组，直到到达没有元素的点（只有一个）。还有一个 single element is always sorted.

参见下面代码中的基本情况：

if(a.length<2) /*Remember this is the base case*/
        {
            return;
        }

一旦到达单个元素，将它们排序并合并回来。这样你就得到了一个完整的排序数组，很容易合并。我们做这些废话的唯一原因是为了获得更好的运行时间算法，即 O(nlogn).

因为所有其他排序算法 (insertion, bubble, and selection) 都需要 O(n2)，这确实太多了。因此，人类必须找出更好的解决方案。这是对人性的需要，非常重要。我知道这很烦人，我已经经历了这些废话。

请在尝试之前对递归做一些研究。清楚地理解递归。远离这一切。举一个简单的递归示例并开始研究它。举一个阶乘的例子。这是一个不好的例子，但很容易理解。

自上而下的合并排序

查看我的代码，它既好又简单。同样，在您第一次尝试时，两者都不容易理解。在你试图理解这些东西之前，你必须接触递归。祝一切顺利。

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

}

Answer 3

这是合并排序的另一种实现方式，这是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;
}
}

合并排序递归

Merge Sort Recursion

java

algorithm

mergesort

自上而下的合并排序