java - 递归 MergeSort 和计数比较

Question

我写了一个程序，包含4种排序方法，选择排序，插入排序，归并排序，递归归并排序。插入和选择排序方法运行良好，并返回给我一个排序列表和适量的比较。我的合并排序方法返回一个排序列表，但我的比较 = 1。我的递归合并排序甚至不对列表进行排序，还说比较 = 1。有人能帮我找到我的错误吗？这是我所有的代码。

public class ArraySort {
    private long[] a;                 // ref to array a
    private int nElems;               // number of data items

    public ArraySort(int max) {       // constructor
       a = new long[max];             // create the array
       nElems = 0;                    // no items yet
    }

    public void Clone(ArraySort c) {  // c is another array
       c.nElems = this.nElems;                                 // Copy nElems
       System.arraycopy(this.a, 0, c.a, 0, this.nElems);       // Copy elements
    }

    public void insert(long value) {  // put element into array
       a[nElems++] = value;           // insert value
    }

    public String toString() {           // displays array contents
       String res="";
       for(int j=0; j<nElems; j++)       // for each element,
          res = res + a[j] + " ";        // append it to res
       return res;
    }

    private int insertOrder(int n, long temp) { // insert temp into a[0..(n-1)]
                  // and keep a[0..n] sorted.
        int count = 0;
        while (n > 0) {
            count++;                       // count next comparison
            if (a[n-1] > temp)   {         // until one is smaller,
               a[n] = a[n-1];              // shift item to right
               --n;                        // go left one position
            } else break;
        }
        a[n] = temp;                      // insert marked item
        return count;
    }

    public int insertionSort() {
        int count = 0;
        for (int n=1; n<nElems; n++)  
            count += insertOrder(n, a[n]);   // insert a[n] into a[0..(n-1)]

        return count;
    } // end insertionSort()

    private void swap(int one, int two) {
       long temp = a[one];
       a[one] = a[two];
       a[two] = temp;
    }

    public int selectionSort() {
       int out, in, max, count=0;

       for(out=nElems-1; out > 0; out--) {  // outer loop
          max = out;                        // max is maximum item's index
          for(in=0; in<out; in++) {          // inner loop
             if(a[in] > a[max] )            // if max is smaller,
                 max = in;                  // we have a new max
             count++;                       // count one comparison
          }
          swap(out, max);                   // swap them
       }  // end for(out)
       return count;
    }  // end selectionSort()

    public int mergeSort() {           // called by main()
        int count = 0;
        long[] workSpace = new long[nElems]; // provides workspace
        recMergeSort(workSpace, 0, nElems-1);
        count++;
        return count;
    }


public int recMergeSort(long[] workSpace, int lowerBound,
        int upperBound) {

    int count = 0;

    if(lowerBound == upperBound)            // if range is 1,
        return 1;

    // find midpoint
    int mid = (lowerBound+upperBound) / 2;

    recMergeSort(workSpace, lowerBound, mid);   // sort low half

    recMergeSort(workSpace, mid+1, upperBound);  // sort high half


    merge(workSpace, lowerBound, mid+1, upperBound); // merge them
    count++;
    return count;

}  // end else
  // end recMergeSort()


private int merge(long[] workSpace, int lowPtr,
        int highPtr, int upperBound)
{
    int j = 0;                             // workspace index

    int lowerBound = lowPtr;

    int mid = highPtr-1;

    int n = upperBound-lowerBound+1;       // # of items

    int count = 0;

    while(lowPtr <= mid && highPtr <= upperBound)

        if( a[lowPtr] < a[highPtr] ) {
            workSpace[j++] = a[lowPtr++];
            count++;
        }

        else {
            workSpace[j++] = a[highPtr++];
            count++;
        }

        while(lowPtr <= mid)
            workSpace[j++] = a[lowPtr++];

        count++;


        while(highPtr <= upperBound)
            workSpace[j++] = a[highPtr++];

        count++;

        for(j=0; j<n; j++)

           a[lowerBound+j] = workSpace[j];

        return count;
    }  // end merge()
}

正在从这里调用方法...

import java.util.*;

public class SortComparison {

    public static void main(String[] args) {

       int count, maxSize = 20;      // array size
       ArraySort arr, carr;           // reference to array
       arr = new ArraySort(maxSize);  // create the arrays
       carr = new ArraySort(maxSize);

       // insert some random numbers
              Random generator = new Random();
       for (int i = 0; i < 20; i++) {
            arr.insert(Math.abs(generator.nextInt())%maxSize);
       }

       System.out.println("Before sort: " + arr);                // display items

       arr.Clone(carr);
       count = carr.insertionSort();          // insertion-sort a clone of arr
       System.out.println("Insert sort: " + carr + " comparions=" + count);                  

       arr.Clone(carr);
       count = carr.selectionSort();          // selection-sort a clone of arr
       System.out.println("Select sort: " + carr + " comparions=" + count); 

       arr.Clone(carr);
       count = carr.mergeSort();
       System.out.println("Merge sort: " + carr + " comparions=" + count);

       arr.Clone(carr);
       count = carr.recMergeSort(null, maxSize, maxSize);
       System.out.println("RecMerge sort: " + carr + " comparions=" + count);

  }  // end main()

}  // end class SortComparison

当程序运行时，这是我收到的输出...

Before sort: 3 2 4 7 17 11 3 0 14 6 8 7 12 15 0 0 9 4 7 16 
Insert sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=94
Select sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=190
Merge sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=1
RecMerge sort: 3 2 4 7 17 11 3 0 14 6 8 7 12 15 0 0 9 4 7 16  comparions=1

谁能帮我解决这个问题!？

---

我不知道为什么我的递归合并排序方法无法对列表进行排序。以及为什么最后两个比较 = 1。

Answer 1

由于这是作业，我将只展示如何修复 mergeSort():

public int mergeSort() {
    int count = 0;
    long[] workSpace = new long[nElems];
    count += recMergeSort(workSpace, 0, nElems-1); // Add the comparisons executed there
    return count;
}

您需要以类似的方式修复 recMergeSort()。

我猜你认为 count 是一个全局变量。但事实并非如此。在您所有的排序方法中，count 是一个局部变量，在方法范围之外是不可见的。因此，如果您修改 recMergeSort() 中的 count 变量，它不会自动影响 mergeSort 中的(其他)count 变量()。将计数从(调用)recMergeSort()“发送”到(调用)mergeSort() 的一种自然方式是通过return count，如你做对了。不幸的是，您没有使用 recMergeSort() 返回的结果。

最后一件事，也许我不够清楚:即使你从 recMergeSort() 递归调用 recMergeSort()，count 调用者中的变量与被调用者中的 count 变量不同。因此，即使您进行递归调用，被调用方法仍然需要通过 return 传递结果，调用方法需要获取它。