快速排序计数器示例

Question

首先（正如问题标题所暗示的）我不是在寻找为什么波纹管分区方法不起作用，而是对其进行修改，以便它适用于以下输入：

int[] a = {1,2,8,4,5,7};

这是 partition 方法以及一些其他内容：

static int[] swap (int[] a,int i,int j){
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
    return a;
}

static int partition (int[] a,int l,int r){
    int i = l;
    int j = r;
    int v = a[l];
    while (true) {

        while (a[i] < v) {
            if (i == r) break;
            i++;
        }

        while (a[j] > v) {
            if (j == l) break;
            j--;
        }

        if (i >= j) break;

        a = swap(a,i,j);
    }

    a = swap(a, l, j);
    return j;
}

void sort(int[] a,int l,int r){
    int j = partition(a, l, r);
    sort(a, l, j-1);
    sort(a, j+1, r);
}

public static void main(String[] args) {

    int[] a = {1,2,8,4,5,7};
    System.out.println(partition(a,0,5));

}

输出：

0

输出是从 partition 方法返回的主元索引。 0，作为枢轴的索引，在定义上是有意义的，即 everything left of the pivot is smaller and everything right of the pivot is larger，但显然运行s 变成了 sort 中的一个问题，即：

sort(a, l, j-1);

你的右指针是负数 (j-1 = 0-1 = -1)。我的问题是，是否对上述方法进行了修改，以保持定义 (everything left of the pivot is smaller and everything right of the pivot is larger) 而不是运行进入 sort 中的问题。

Answer 1

缺少的部分是行

if ( l >= r ) return;

在 sort 方法的开头。这实际上是递归停止步骤，因此无论如何都有必要拥有它以防止无休止的递归。但除此之外，它还解决了你的问题，因为如果你调用 sort(0,-1) 那么 -1 小于 0，所以它阻止了对该索引的进一步处理。

快速排序计数器示例

Quicksort Counter Example

java

algorithm

quicksort