java - 如何将 "glue"排序分区恢复为排序分区？ (快速排序Java实现)

Question

我已经测试过我的分区算法运行良好，但是当在实现中使用它时，我得到一个未排序的数组。由于这是针对一个类的，因此我需要编写该类本身，以便我可以将答案作为字符串返回。我的问题很可能出在 qkSort() 方法中。代码如下:

private static int splitterElement;

public static void main (String[] args){
    System.out.println(myMethod());
}

public static String myMethod() {
    String result = "";
    int[] testArray = null;
    testArray = populateArray(testArray, 7, 10);

    result += "Before sort: \n" + printArray(testArray);
    testArray = qkSort(testArray,1,testArray.length);
    result += "After sort: \n" + printArray(testArray);
    return result;
}

//Method to continually call the partition() method
public static int[] qkSort(int[] x, int left, int right){
    if (right - left >= 1) {
        //after running this method, the global variable splitterElement is assigned.
        x = partition(x,left,right);

        qkSort(x,left,splitterElement-1);
        qkSort(x,splitterElement + 1,right);
    }

    //base case. if right-left = 0, then the array length is 1, 
    //and that is already sorted
    return x;
}




/**
 * Populates an integer array with random integers. Should be used only with
 * non-itialized integer arrays. 
 * 
 * @param x an uninitialized array of integers and will be returned once it is populated.
 * @param sizeOfArray The size that array x will be initialized to.
 * @param rangeOfValues The range of values that that each element can be. This value should
 * not surpass the maximum value for integers, but no error-checking is performed. 
 * @return
 */
public static int[] populateArray (int[] x, int sizeOfArray, int rangeOfValues){
    x = new int[sizeOfArray];
    for (int i = 0; i < sizeOfArray; i++){
        x[i] = (int)(Math.random() * rangeOfValues); //place a random number from 0 to rangeOfValues into array.
    }
    return x;
}

/**
 * 
 * @param x An integer array. It is assumed that x is initialized when the method is called.
 * @param left
 * @param right The length of the array can be used for the right int.
 * @see #populateArray(int[], int, int)
 * @return
 */
public static int[] partition (int[] x, int left, int right){
    //element of the splitter
    int l = (int) (Math.random() * x.length);
    splitterElement = l;
    x = swap (x,left,l);

    //value of the splitter
    int t = x[left];

    int i = left;
    for (int j = left + 1; j < right; j++){
        if (x[j] < t){
            i++;
            x = swap (x,i,j);
        }
    }
    x = swap(x,left,i);
    return x;
}

/**
 * Places the value at index1 in index2, and places the value at index2 in index1.
 * 
 * @param array The array that will be worked on.
 * @param index1 The first place we will switch values. 
 * @param index2 The second place we will switch values.
 * @return
 */
public static int[] swap (int[] array, int index1, int index2){
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
    return array;
}

/**
 * A simple print method that prints an array.
 * @param array Input.
 */
public static String printArray (int[] array){
    String result = "";
    for (int i = 0; i < array.length; i++){
        result += array[i] + " ";
    }
    result += "\n";
    return result;
}

}

输出:

排序前:8 9 7 3 4 2 6

排序后:8 6 3 9 7 2 4

感谢您对我的问题有任何想法!

Answer 1

我在您的代码中发现了几个问题:

1)方法不需要返回数组，您可以找到更好的返回值用途

2) 使用全局变量 splitterElement 不起作用，因为它的值可能会在第一次递归调用 qkSort 期间发生变化。方法partition可以返回它的值而不是返回数组，这是没有用的。

3)第一行分区方法:

int l = (int) (Math.random() * x.length);

应该是:

int l = left + (int) (Math.random() * (right - left));

因为您要划分左右范围，而不是整个数组。