java - 实现以中间元素为轴心的快速排序

Question

我尝试并编写了一个以中间元素为中心的快速排序代码。

我成功地写了一篇。

但是 Pivot 具有以下属性:

它左边的元素小于 pivot 而右边的元素更大。

我无法在下面的代码中实现这一点。

private static void QuickSortAlgorithm(int[] a, int i, int n) 
{
    if(i<n)
    {
        int part = partition(a,i,n);

        QuickSortAlgorithm(a, i, part-1);

        QuickSortAlgorithm(a, part, n);
    }
}

private static int partition(int[] a, int i, int n) 
{
    int pivot = (i+n)/2;

    int left = i;

    int right = n;
    while(left<=right)
    {
        while(a[left]<a[pivot]){
            left++;
        }

        while(a[right]>a[pivot])
        {
            right--;
        }

        if(left<=right)
        {
            swap(a,left,right);
            left++;
            right--;
        }
    }
    return left;

}

主要方法:

    int a[]={5,7,3,9,1};
    int n = a.length;
    QuickSortAlgorithm(a,0,n-1);
    System.out.println(Arrays.toString(a));

我的疑问是:

我将向左发送作为我的分区索引。

但是，当我递归调用 QuickSortAlgorithm() 时

我正在发送 i 到 part-1 和 part 到 n;

我应该发送什么作为分区索引，以便

我可以这样调用:所以枢轴属性是否满足？

    QuickSortAlgorithm(a, i, part-1);

    QuickSortAlgorithm(a, part+1, n);

谢谢:)

Answer 1

您必须在第一个堆栈调用中发送枢轴值(包括在内)并将枢轴+1 作为第二个堆栈调用的较​​低索引。您还必须将 left 的值设置为 i+1 然后您的代码将给出正确的输出