用Java中的隨機數據快速排序

Question

我已經被分配用一個隨機支點快速排序（因爲它被認爲是最有效率/最安全的方式），但我一直在追隨一個bogosort。任何人都可以指導我如何做到這一點？有人可以幫我看看我的寶貝，看看我能否挽救它嗎？

public static void Quick(int[] target, int lo, int hi) { 
    if(hi-lo==0){return;} 
    Random numberGenerator = new Random(); 
    int pivot = (numberGenerator.nextInt(hi-lo)+lo); 
    int high; 
    for(high=hi; high>pivot ; high--){ 
     if(target[high]<target[pivot]){ //if highest was smaller than pivot, move far end 
      if(high-pivot==1){ 
       int temp=target[high]; 
       target[high]=target[pivot]; 
       target[pivot]=temp; 
      } 
      else{ 
       int temp1 = target[pivot]; 
       int temp2 = target[pivot+1]; 
       target[pivot]=target[high]; 
       target[pivot+1]=temp1; 
       target[high]=temp2; 
      } 
     } 
    } 
    int low; 
    for(low=lo; low<pivot ; low++){ 
     if(target[low]>target[pivot]){ //if highest was smaller than pivot, move far end 
      if(pivot-low==1){ 
       int temp=target[low]; 
       target[low]=target[pivot]; 
       target[pivot]=temp; 
      } 
      else{ 
       int temp1 = target[pivot]; 
       int temp2 = target[pivot-1]; 
       target[pivot]=target[low]; 
       target[pivot-1]=temp1; 
       target[low]=temp2; 
      } 
     } 
    } 
    if(low-lo>0){ 
     Quick(target, lo, low-1); 
    } 
    if(hi-high>0){ 
     Quick(target, high+1, hi); 
    } 
} 

Answer 1

看到這個僞碼，就地patitioning（維基百科）：

function partition(array, left, right, pivotIndex) 
    pivotValue := array[pivotIndex] 
    swap array[pivotIndex] and array[right] // Move pivot to end 
    storeIndex := left 
    for i from left to right - 1 // left ≤ i < right 
     if array[i] ≤ pivotValue 
      swap array[i] and array[storeIndex] 
      storeIndex := storeIndex + 1 
    swap array[storeIndex] and array[right] // Move pivot to its final place 
    return storeIndex 

注意到它通過全陣列式循環（除了最後索引）。主軸直到結束才交換。在你的代碼中，透視值通過循環看起來不正確。

每次出現swap時，swap對象（storeIndex都會改變）。

此外，您只需要將低於主鍵的值交換到左側。如果所有的低值都在左邊，那麼高值將會在右邊。