带随机轴的快速排序

Question

我正在尝试通过生成边界从低到高的随机数并取它们的中值来实现一个带有随机基准的 QuickSort 版本。

但是，当我这样做时，代码运行得非常慢。如果我尝试对包含 29 个元素的数组进行排序，它会在 2 秒内运行，但一旦我将大小增加到 30+（包括 (30)），算法就会运行得非常慢。对包含 30 个元素的数组进行排序大约需要 10 秒以上，如果我做得更好，你就会明白了。

如果我有一个固定的枢轴点，这不是问题。我可以毫无问题地对大小为 100 000 的数组进行排序。

我不知道出了什么问题，需要一些帮助来弄清楚为什么我生成随机轴心点时运行这么慢。

此致！

protected int Partition(int[] v, int low, int high, boolean FixedPivot)
{
    int pivot = 0;
    if(!FixedPivot)
        pivot = RandomPivot(v, low, high); //If I pick a random pivot point then it runs extremly slow for some reason.
    else
        pivot = FixedPivot(v, low, high); //This one works fine, I can sort quickly without any problem.

    int i = low - 1;
    int j = high + 1;
    while(true)
    {
        do j--; while(v[j] > pivot);
        do i++; while(v[i] < pivot);
        if(i < j)
            Swap(v, i, j);
        else
            return j;
    }
}
protected int FixedPivot(int[] v, int low, int high)
{
    int average = (low + high) / 2;
    return Math.max(Math.min(v[low], v[average]), Math.min(Math.max(v[low], v[average]), v[high]));
}
protected int RandomPivot(int[] v, int low, int high)
{
    int X = 0;
    int Y = 0;
    int Z = 0;
    Random random = new Random();
    int range = (high - low) + low;
    if(range > 0)
    {
        X = random.nextInt(range);
        Y = random.nextInt(range);
        Z = random.nextInt(range);
    }
    return Math.max(Math.min(v[X], v[Y]), Math.min(Math.max(v[X], v[Y]), v[Z]));
}

Answer 1

我认为问题在于 random.nextInt(range); 在 0 和 high 之间，而您希望它在 low 和 high 之间。修复方法如下：

int range = (high - low);
if(range > 0)
{
    X = random.nextInt(range) + low;
    Y = random.nextInt(range) + low;
    Z = random.nextInt(range) + low;
}

带随机轴的快速排序

QuickSort with Random Pivot

java

sorting

algorithm

quicksort