Java 中的就地快速排序

为了刷新一些 Java，我尝试实现一个可以对整数数组进行排序的快速排序（就地）算法。以下是我到目前为止得到的代码。你可以通过以下方式调用它sort(a,0,a.length-1).

如果两个“指针”都存在，则此代码显然会失败（进入无限循环）i,j每个都指向与枢轴具有相同值的数组条目。枢轴元素v始终是当前分区的最右边（索引最大的分区）。

但我就是不知道如何避免这种情况，有人看到解决方案吗？

static void sort(int a[], int left, int right)   {
    if (right > left){
        int i=left, j=right-1, tmp;
        int v = a[right]; //pivot
        int counter = 0;
        do {
            while(a[i]<v)i++;
            while(j>0 && a[j]>v)j--;

            if( i < j){
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        } while(i < j);
        tmp = a[right];
        a[right] = a[i];
        a[i] = tmp;
        sort(a,left,i-1);
        sort(a,i+1,right);

    }
}    

在执行快速排序时，我强烈建议创建一个单独的分区方法，以使代码更易于理解（我将在下面展示一个示例）。除此之外，避免最坏情况运行时间的一个好方法是在执行快速排序之前对正在排序的数组进行洗牌。此外，我使用第一个索引而不是最后一个索引作为分区项。

例如：

public static void sort (int[] a)
{
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
}

private static void sort(int[] a, int lo, int hi)
{
    if (hi <= lo) return;
    int j = partition(a, lo, hi) // the addition of a partitioning method
    sort(a, lo, j-1);
    sort(a, j+1, hi);
}

private static int partition(int[] a, int lo, int hi)
{
    int i = lo, j = hi + 1, tmp = 0;
    int v = a[lo];
    while (true)
    {
         while (a[i++] < v) if (i == hi) break;
         while (v < a[j--]) if (j == lo) break;
         if (i >= j) break;
         tmp = a[i];
         a[i] = a[j];
         a[j] = tmp;
    }
    tmp = a[lo];
    a[lo] = a[j];
    a[j] = temp;
    return j;
}

除此之外，如果您想要一个关于快速排序如何工作的非常好的示例（作为复习），请参阅here.