java - 三向排序算法

Question

我已经用 Java 实现了一个三向排序算法。假设我有以下数组:

int myArray[] = {8,3,5,7,9,2,3,5,5,6}

显然，我需要成为 2 3 3 5 5 5 6 7 8 9。除了“2”之外，我的算法工作正常。事实上，我得到以下输出:

3 3 5 5 5 6 7 2 8 9 

我不知道为什么...

/* 
     * DESCRIPTION OF mergeThreeWay ALGORITHM
     * 
     * merges sorted subarrays A[start...firstThird], A[firstThird+1,secondThird], and A[secondThird+1,stop]
     * 
     * There are 3 possible cases when one merges :
     *  1) all 3 sub-arrays have elements left
     *  2) only 2 sub-arrays have elements left
     *  3) only 1 sub-arrays have elements
     *  
     * What action to take?
     *  For case 1) select the smallest element from the 3 sub-arrays and add it to the temporary array
     *           2) select the smallest element from the 2 sub-arrays and add it to the temporary array
     *           3) this sub-array is sorted - add all elements to the temporary array
     * 
     * Finally, copy the temporary array to the original array
     * 
     * The algorithm uses while loops to iterate trough the sub-arrays until one sub-array has no elements left (all of its elements have been copied to the temp array)
     */
    public static void mergeThreeWay(int A[], int start, int firstThird, int secondThird, int stop) {
        int p1 = start;
        int p2 = firstThird;
        int p3 = secondThird;

        int tmp[] = new int[A.length];  // I need a temporary array of the same size as A because the sub-arrays keep their index, for example, a sub-array would look like this : [0, 0, 0, 0, 2, 9, 0, 0, 0, 0]  
        int tmpIndex = start;

        // As long as tmpIndex as not reached the end of the array, execute the loop
        while(tmpIndex <= stop) {

            // Get the smallest elements of the three sub-arrays
            while (p1 < firstThird && p2 < secondThird && p3 <= stop) {
                if (A[p1] <= A[p2] && A[p1] <= A[p3]) {
                    tmp[tmpIndex++] = A[p1++];
                }
                else if (A[p2] <= A[p1] && A[p2] <= A[p3]) {
                    tmp[tmpIndex++] = A[p2++];
                }
                else if (A[p3] <= A[p1] && A[p3] <= A[p2]) {
                    tmp[tmpIndex++] = A[p3++];
                } else {
                    tmpIndex++;
                }
            }

            // Get the smallest elements of the two remaining sub-arrays
            while (p1 < firstThird && p2 < secondThird) {
                if (A[p1] <= A[p2]){
                    tmp[tmpIndex++] = A[p1++];
                } else{
                    tmp[tmpIndex++] = A[p2++];
                }
            }

            while (p1 < firstThird && p3 < stop) {
                if (A[p1] <= A[p3]) {
                    tmp[tmpIndex++] = A[p1++];
                } else {
                    tmp[tmpIndex++] = A[p3++];
                }
            }

            while (p2 < secondThird && p3 < stop) {
                if (A[2] <= A[p3]) {    
                    tmp[tmpIndex++] = A[p2++];
                } else {
                    tmp[tmpIndex++] = A[p3++];
                }
            }

            // Complete with the remaining elements

            while (p1 < firstThird) tmp[tmpIndex++] = A[p1++];

            while (p2 < secondThird) tmp[tmpIndex++] = A[p2++];

            while (p3 <= stop) tmp[tmpIndex++] = A[p3++];

            tmpIndex++;
        }

        System.out.println(Arrays.toString(tmp));
        for(int k=start; k <= stop; k++) {
            A[k] = tmp[k];
        }
    }

主要方法

public static void main (String args[]) throws Exception {

    int myArray[] = {8,3,5,7,9,2,3,5,5,6}; // an example array to be sorted. You'll need to test your code with many cases, to be sure it works.

    mergeSortThreeWay(myArray,0,myArray.length-1);

    System.out.println("Sorted array is:\n");
    for (int i=0;i<myArray.length;i++) {
        System.out.print(myArray[i]+" ");
    }
    }
}

mergeSortThreeWay

 // sorts A[start...stop]s the same as the element at 
    public static void mergeSortThreeWay(int A[], int start, int stop) {

        if(start < stop) {

            // DIVIDE
            int firstThird = start + (stop - start) / 3;
            int secondThird = start + 2 * (stop - start) / 3;

            // CONQUER
            mergeSortThreeWay(A, start, firstThird);            // A[start..midLeft] SORTED
            mergeSortThreeWay(A, firstThird+1, secondThird);        // A[midLeft..midRight] SORTED
            mergeSortThreeWay(A, secondThird+1, stop);          // A[midRight..stop] SORTED

            // MERGER
            mergeThreeWay(A, start, firstThird, secondThird, stop);
        }
    }

Answer 1

您的示例运行良好，请自行查看:http://ideone.com/95AR6I

public static void main (String[] args) throws java.lang.Exception
{
    int myArray[] = {8,3,5,7,9,2,3,5,5,6};
    mergeThreeWay(myArray,0,1,5,9);
}

输出:

[2, 3, 3, 5, 5, 5, 6, 7, 8, 9]