用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都会改变）。

此外，您只需要将低于主键的值交换到左侧。如果所有的低值都在左边，那么高值将会在右边。