如何将排序分区"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时可能会改变。方法分区可以返回它的值，而不是返回数组，这是无用的。

3)第一行分区方法:

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

应:

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