java - 在 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）都应该改变。

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