使用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

请参阅以下伪代码以进行就地修补（来自Wikipedia）：

  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）都应更改。

同样，您只需要交换小于左侧枢轴的值。如果所有低值都在左侧，则高值将最终在右侧。