快速排序與隨機樞軸

Question

我想實現一個版本的快速排序與隨機數據透過選擇產生隨機數的邊界由低到高，並採取他們的中位數。

但是，當我這樣做時，代碼運行速度非常緩慢。如果我嘗試使用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; 
}