帶隨機分區的QSort

Question

下面的qsort實現來自「算法基礎」一書，因此被認爲是正確的。以下是我在Java中的實現。這是行不通的。問題是當隨機選擇分區時，生成的分區不正確。我希望有人能告訴我什麼，我做錯了：

鮑勃

import java.util.*; 
public class qsort { 
    public static void main(String []args) 
    { 
     int []a1 = { 1, 2, 3, -4, -5, 6, 7 }; 
     sort(0, a1.length-1, a1); 
     printarray (a1); 

    } 
static void sort(int low, int high, int []a) 
{ 
    if (low < high) { 
     int p = part(low, high, a); 
     System.out.println(" p = " + p); 
     printarray(a, low, p); 
     System.out.println(); 
     sort(low, p-1, a); 
     printarray(a, p, high); 
     System.out.println(); 
     sort(p+1, high, a); 
    } 
} 
static int part(int low, int high, int [] S) { 
     int i; 
     int j; 
     int randspot; 
     int pivotitem; 
     int pivotpoint; 
     Random random = new Random(456); 
     randspot = random.nextInt(high-low +1)+low; 
     pivotitem = S[randspot]; 
     j = low; 
     for (i = low + 1; i <= high; i++) 
      if (S[i] < pivotitem){ 
       j++; 
       int temp = S[j]; 
       S[j] = S[i]; //exchanges S[i] and S[j] 
       S[i] = temp; 
      } 
     pivotpoint = j; 
     int temp = S[low]; 
     S[low] = S[pivotpoint]; 
     S[pivotpoint] = temp; 
     return pivotpoint; 
    } 

static void printarray (int [] Test){ 
    for (int i = 0; i<Test.length; i++){ 
     if (i !=0 && i%10==0) 
      System.out.println(); 
     System.out.print(Test[i]+ "\t"); 

    } 
} 
static void printarray (int [] Test, int low, int high){ 
    for (int i = low; i<high; i++) 
     System.out.print(Test[i]+ "\t"); 
    } 
} 

Answer 1

你需要換首先用低度元件樞軸元素，然後做其他操作。檢查我在下面的代碼塊中添加的代碼。

static int part(int low, int high, int [] S) { 
    int i; 
    int j; 
    int randspot; 
    int pivotitem; 
    int pivotpoint; 
    Random random = new Random(456); 
    randspot = random.nextInt(high-low +1)+low; 
    System.out.println(" p = " + randspot); 
    System.out.println(" value = " + S[randspot]); 
    pivotitem = S[randspot]; 
    //---------------Start code block 
    int temp1 = S[randspot]; 
    S[randspot] = S[low]; 
    S[low] = temp1; 
    //---------------End code block 
    j = low; 
    for (i = low + 1; i <= high; i++) 
     if (S[i] < pivotitem){ 
      j++; 
      int temp = S[j]; 
      S[j] = S[i]; //exchanges S[i] and S[j] 
      S[i] = temp; 
     } 
    pivotpoint = j; 
    int temp = S[low]; 
    S[low] = S[pivotpoint]; 
    S[pivotpoint] = temp; 
    return pivotpoint; 
}