在Java中使用随机枢轴的快速排序

Question

在Java中使用随机枢轴的快速排序

5

我被指派实现一个使用随机枢轴点的快速排序算法（因为这是最高效/最安全的方式），但我一直在苦苦寻找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);
    }
}

- Dan

1

你的Random实例不应该是一个局部变量。 - Brian S

@Brian S，即使如此，它也不能解决我的问题。 - Dan

1

这就是为什么它是一条评论而不是答案的原因 :) - Brian S

@Brian S. - 啊，你说得对，哈哈哈。 - Dan

什么是Bogosort的意思？ - Hengameh

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fgb · Accepted Answer

以下是维基百科上的原地划分（inplace partitioning）伪代码：

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

此外，只需要将低于枢轴的值向左交换。如果所有低值都在左侧，则高值将最终位于右侧。