java - 尝试通过一些修改来实现合并排序

Question

我正在尝试通过一些优化来实现合并排序算法，例如仅使用临时存储一次并避免复制到最后。一切都很好，除了一些之外，许多测试文件都通过了。这里发生的事情是使用未排序的数组，算法显示了一些问题。我在代码中编写了打印语句试图解决问题，但无法做到这一点。由于许多测试都通过了，我相信程序中没有什么重大错误，只是它遗漏了一些东西。

我尝试过实现这个程序，它在很多方面都是成功的，只有 3 个案例没有通过。但是，我面临的主要问题是测试用例 Mergesort_two() 没有通过，因为它很简单。只是调用两个数字并以排序的形式断言，但我的程序拒绝了它。我相信这是一个我无法弄清楚的小错误。

public static void mergesort(int[] input, int[] temp, 
                             int start, int end, 
                             boolean intoTemp) {
    if (start == end) {
        return; 
    }

    if ((start + 1) == end) {
        if (intoTemp == true) {
            temp[start] = input[start];
            return;
        }
    }

    if (start < end) {
        if (intoTemp == false) {
            intoTemp = true;
            int mid = (start + end)/2;

            mergesort(input, temp, start, mid, intoTemp);
            mergesort(input, temp, mid, end, intoTemp);

            merge(input, temp, start, mid, end);
            System.out.println("Input Array: " + Arrays.toString(input) + 
                    " Temp: " + Arrays.toString(temp) + " intoTemp: " +
                    intoTemp + "Start Mid End: " + start + " " + mid + " " + end);

        }
        else if(intoTemp == true) {
            intoTemp = false;
            int mid = (start + end)/2;

            mergesort(input, temp, start, mid, intoTemp);
            mergesort(input, temp, mid, end, intoTemp);

            merge(temp, input, start, mid, end);
            System.out.println("Input Array: " + Arrays.toString(input) + 
                    " Temp: " + Arrays.toString(temp) + " intoTemp: " +
                    intoTemp + "Start Mid End: " + start + " " + mid + " " + end);

        }
    }
    if (start == 0 && end == input.length) {
        System.arraycopy(temp, 0, input, 0, input.length);
    }
}

/** Merges input[start...mid-1] with input[mid...end-1] into
 * output[start...end-1]. The input array should not be modified at
 * all, and only start...end-1 of the output array should be changed. 
 * 
 * @param input  Input array
 * @param output Output array
 * @param start  Starting index
 * @param mid    Midpoint index
 * @param end    Ending index+1
 */
public static void merge(int[] input, int[] output, 
                         int start, int mid, int end) {

    if (input == null || (start == mid && mid == end)) {
        return;
    }

    int i = start;
    int j = mid - 1;
    int k = mid;

    int index = start;

    while (i <= j && k < end) {
        if (input[i] <= input[k]) {
            output[index] = input[i];
            i++;
            index++;
        }
        if (input[i] > input[k]) {
            output[index] = input[i];
            k++;
            index++;
        }
    }    

    while (i <= j) {
        output[index] = input[i];
        index++;
        i++;
    }

    while (k < end) {
        output[index] = input[k];
        index++;
        k++;
    }
  }
}

//////测试用例

 @Test
public void testMergesort_Two() {
    System.out.println("mergesort one element");
    int[] array = new int[2];

    // Already sorted
    array[0] = 10; array[1] = 13;       
    CSSE240_Assign4.mergesort(array);
    assertEquals(array[0], 10);
    assertEquals(array[1], 13);

    // Unsorted
    array[0] = 3; array[1] = -4;
    CSSE240_Assign4.mergesort(array);        
    assertEquals(array[0], -4);
    assertEquals(array[1], 3);        
}

@Test
public void testMergesort_Large() {
    System.out.println("mergesort one large");
    Random rng = new Random();

    for(int s = 3; s < 20; ++s) {

        int[] array = new int[s];
        int[] orig = new int[s];

        // Fill with random values.
        for(int i = 0; i < s; ++i) {
            array[i] = rng.nextInt();
            orig[i] = array[i];
        }

        CSSE240_Assign4.mergesort(array);
        Arrays.sort(orig);

        // Make sure both arrays agree
        for(int i = 0; i < s; ++i)
            assertEquals(orig[i], array[i]);                                                
    }
}
@Test
public void testMergeInterleaved() {
    // Various cases where the left/right halves are interleaved. We test
    // this by picking a modulo m and moving all the elements where 
    // e % m < m/2 to the right side.
    System.out.println("merge reverse sorted");

    for(int s = 3; s < 20; ++s) {
        int[] array = new int[s];
        int mid = 0;       

        // Move the elements of the array around into the two halves.
        for(int m = 2; m < 5; ++m) {                

            // Populate the array with 0...s-1
            for (int i = 0; i < s; ++i) {
                array[i] = i;
            }

            int[] left = new int[s];
            int[] right = new int[s];
            int lc = 0, rc = 0;

            for(int i = 0; i < s; ++i)
                if(array[i] % m < m/2) 
                    right[rc++] = array[i];
                else
                    left[lc++] = array[i];

            // Copy back into the array
            int j = 0;
            for(int i = 0; i < lc; ++i)
                array[j++] = left[i];
            for(int i = 0; i < rc; ++i)
                array[j++] = right[i];

            mid = lc; // Midpoint            

            int[] output = new int[s];
            Arrays.fill(output, -1);

            // TODO: check different endpoints...
            CSSE240_Assign4.merge(array, output, 0, mid, s);

            for(int i = 0; i < s; ++i)
                assertEquals(output[i], i);
        }
    }
}       


testMergesort_Two Failed : expected <-4> but was <3>
testMergeInterleaved Failed: expected <0> but was <1>
testMergeSort_Large Failed : expected:<-1131373963> but was:<-2038582366>

Answer 1

评论中注明的更改。

    public static void mergesort(int[] input, int[] temp, 
                                 int start, int end, 
                                 boolean intoTemp) {
        if (start == end) {
            return; 
        }

        if ((start + 1) == end) {
            if (intoTemp == true) {
                temp[start] = input[start];
                return;
            }
        }

        if (intoTemp == false) {
            intoTemp = true;
            int mid = (start + end)/2;
            mergesort(input, temp, start, mid, intoTemp);
            mergesort(input, temp, mid, end, intoTemp);
            merge(temp, input, start, mid, end);
        } else {
            intoTemp = false;
            int mid = (start + end)/2;
            mergesort(input, temp, start, mid, intoTemp);
            mergesort(input, temp, mid, end, intoTemp);
            merge(input, temp, start, mid, end);
        }
    }

    public static void merge(int[] input, int[] output, 
                             int start, int mid, int end) {
        int i = start;
        int j = mid;                          // using j instead of k
                                              // and mid instead of j

        int index = start;

        while (i < mid && j < end) {          // using mid
            if (input[i] <= input[j]) {
                output[index] = input[i];
                i++;
                index++;
            } else {                          // change
                output[index] = input[j];     // was input[i]
                j++;
                index++;
            }
        }    

        while (i < mid) {                     // using mid
            output[index] = input[i];
            i++;                              // changed order for consistency
            index++;
        }

        while (j < end) {
            output[index] = input[j];
            j++;                              // changed order for consistency
            index++;
        }
    }