数组中间随机枢轴的快速排序算法

Question

我必须编写一个带有随机主元的快速排序算法，所以我创建了以下代码：

public void quickSort(int left, int right)
{
    if(a.length == 1)
    {
        System.out.println("Only one element.");
    }
    else
    {
        int l = left;
        int r = right;
        if(right > left)
        {
            Random rand = new Random();
            int num = left + rand.nextInt(right - left);
            int p = a[num];

            int tmp = a[r];
            a[r] = a[num];
            a[num] = tmp;
            num = r;
            r--;


            while(r > l)
            {
                while((l<right)&&(a[l]<=p))
                {
                    l++;
                }
                while((r > left)&&(a[r]>=p))
                {
                    r--;
                }
                if(l < r)
                {
                    tmp = a[l];
                    a[l] = a[r];
                    a[r] = tmp;
                }
            }

            if(a[l] > p) {
                tmp = a[l];
                a[l] = a[num];
                a[num] = tmp;
            }

            quickSort(left,l-1);
            quickSort(l+1,right);
        }

       }
    }

"a" 应该是一个整数数组。如您所见，一旦我得到我的随机枢轴，我就将它与数组的最后一个元素交换，这样我的算法就不会出现任何问题，但我想知道是否有可能让枢轴保持在它的位置尽管如此，随机位置并毫无问题地对其进行排序。提前致谢。

Answer 1

是的，有。基本上，我们可以使不等式更严格：将 a[l]<=p 更改为 a[l]<p，将 a[r]>=p 更改为 a[r]>p。这将有助于处理数组中也可以有相等元素的情况，因此您可以摆脱 l<right 和 left<r 条件。

枢轴不能保证精确地落在 l 位置，那么，a[left...l] 仍将是 <=p，a[l+1...right] 将是 >=p, 这足以让算法工作。

这是您的代码的一个变体。条件 if(l < r) 修改为 if(l <= r)，并在内部添加 l++; 和 r--; 以跳过我们刚刚交换的两个元素。此外，递归调用更新为 (left,r) 和 (l,right)，因为现在没有保证枢轴元素的位置。

public void quickSort(int left, int right)
{
    if(a.length == 1)
    {
        System.out.println("Only one element.");
    }
    else
    {
        int l = left;
        int r = right;
        if(right > left)
        {
            Random rand = new Random();
            int num = left + rand.nextInt(right - left);
            int p = a[num];

            while(r > l)
            {
                while(a[l]<p)
                {
                    l++;
                }
                while(a[r]>p)
                {
                    r--;
                }
                if(l <= r)
                {
                    int tmp = a[l];
                    a[l] = a[r];
                    a[r] = tmp;
                    l++;
                    r--;
                }
            }

            quickSort(left,r);
            quickSort(l,right);
        }
    }
}

数组中间随机枢轴的快速排序算法

Quicksort algorithm with random pivot in the middle of the array

java

random

algorithm

quicksort