需要帮助JAVA快速排序递归

Question

对于学校，我必须为字符串数组编写快速排序。我认为我的分区是好的，但我总是得到错误的递归。

public static int partition(String[] input, int max) {
    // pivot is dividing point
    // I keeps track of lesser values
    // count is just a counter
    // Pivots in place
    int pivot = 0;
    int i = 1;
    int count = 1;
    while (count <= max) {
        if (input[count].compareTo(input[pivot]) < 0) {
            input[i] = input[count];
            i = i + 1;
        }
        if (count == max) {
            input[i] = input[pivot];
            input[pivot] = input[i];
        }
        count++;
    }
    return pivot;
}
public static void qSort(String[] input) {
    int index = partition(input, input.length - 1);
    int count = 0;
    if (count < index - 1) {
        partition(input, index - 1);
    }
    if (index + 1 < count && count < input.length) {
        partition(input, input.length - 1);
    }
    count++;
}

Answer 1

你的实现有很多错误。首先，你总是选择主元素作为数组下标为0的元素。快速排序的思想是，你选择一个主节点，围绕它划分数组，然后递归地在选定的主节点周围的两个分区上应用快速排序。如何识别将在其上递归调用快速排序的分区的开始和结束?您需要像其他人在评论中提到的那样，将这些参数传递给分区方法，对于快速排序方法本身也是如此。

public void swap (String [] array, int i, int j) {
    String tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
public static int partition (String [] array, int low, int high) {
    String pivot = array[low];
    int index = low+1;
    for (int i = low+1; i <= high; i++) {
        if (pivot.compareTo(array[i]) > 0) {
            swap(array, i, index);
            index++;
        }
    }
    swap(array, low, index-1);
    return index-1;
}
public static void qsort(String [] array, int low, int high) {
    if (low < high) {
        int p = partition(array, low, high);
        qsort(array, low, p);
        qsort(array, p+1, high);
    }
}

显然，这不是选择枢轴的最佳方式，因为某些数组会使算法执行得很差。更好的方法是每次使用随机枢轴。