使用Java中的随机数据点快速排序

Question

我被分配去实现一个带有随机枢轴点的快速排序（因为这被认为是最有效/最安全的方法），但是我一直在忙于Bogosort。谁能指导我该怎么做？有人可以帮我看看我的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

请参阅此伪代码以进行就地分区（来自维基百科）：

  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

注意它遍历整个数组（最后一个索引除外）。直到最后才交换枢轴。在您的代码中，枢轴值在循环中不断变化，这似乎不正确。

每次交换时，交换目标（上面的 storeIndex）都应该改变。

此外，您只需要交换低于左侧枢轴的值。如果所有低值都在左侧，那么高值将在右侧结束。