如何在快速排序算法中实现递归

Question

我正在尝试在Java中实现快速排序来学习基本算法。我了解算法的工作原理(并且可以在纸上完成(，但发现很难用代码编写它。我已经设法完成了将所有小于枢轴的元素放在左侧，将较大的元素放在右侧的步骤(请参阅下面的代码(。但是，我不知道如何实现算法的递归部分，因此对左右两侧进行递归排序。请帮忙吗？

public void int(A, p, q){
    if(A.length == 0){ return; }
    int pivot = A[q];
    j = 0; k = 0;
    for(int i = 0; i < A.length; i++){
        if(A[i] <= pivot){
            A[j] = A[i]; j++;
        }
        else{
            A[k] = A[i]; k++;
        }
    }
    A[j] = pivot;
}

Answer 1

大免责声明：我没有写这段代码，所以不需要赞成票。但是我链接到一个教程，该教程详细解释了快速排序。也给了我一个非常需要的算法更新！给出的示例有非常好的注释，可能会帮助您了解它。

我建议你根据你的代码调整它，并为它编写som测试来验证它是否有效

快速排序

是一种快速、递归、不稳定的排序算法，它采用分而治之原则。在最好的情况下，快速排序会将数组分成几乎两个相同的部分。如果数组包含 n 个元素，那么第一次运行将需要 O(n(。对其余两个子数组进行排序需要 2 O(n/2(。这最终导致 O(n log n( 的性能。在最坏的情况下，快速排序在每次迭代中只选择一个元素。所以它是O(n( + O(n-1( + (On-2(。O(1( 等于 O(n^2(。

public class Quicksort  {
private int[] numbers;
private int number;
public void sort(int[] values) {
    // check for empty or null array
    if (values ==null || values.length==0){
        return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
}
private void quicksort(int low, int high) {
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    int pivot = numbers[low + (high-low)/2];
    // Divide into two lists
    while (i <= j) {
        // If the current value from the left list is smaller than the pivot
        // element then get the next element from the left list
        while (numbers[i] < pivot) {
            i++;
        }
        // If the current value from the right list is larger than the pivot
        // element then get the next element from the right list
        while (numbers[j] > pivot) {
            j--;
        }
        // If we have found a value in the left list which is larger than
        // the pivot element and if we have found a value in the right list
        // which is smaller than the pivot element then we exchange the
        // values.
        // As we are done we can increase i and j
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }
    // This is the recursion part you had trouble with i guess?
    // Recursion
    if (low < j)
        quicksort(low, j);
    if (i < high)
        quicksort(i, high);
}
private void exchange(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}
}

链接到教程