使用Java中的随机数据库快速排序 [英] Quick Sort with random pivot in Java

问题描述

我被指派用一个随机的枢轴点实现快速排序（因为它被认为是最有效/最安全的方式），但我一直在奴役一个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]）{//如果最高值小于pivot，则移动远端
 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]）{//如果最高值小于pivot，则移动远端
 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）; 
} 
} 
  

解决方案

参见这个伪代码用于inplace patitioning（来自维基百科）：

  function partition（array，left，right，pivotIndex）
 pivotValue ：= array [pivotIndex] 
 swap array [pivotIndex] and array [right] //将pivot移动到结束
 storeIndex：= left 
 for i从左到右 -  1 //left≤我<对于
如果array [i]≤papleValue
 swap array [i]和array [storeIndex] 
 storeIndex：= storeIndex + 1 
 swap array [storeIndex]和array [right] //将枢轴移动到最终位置
返回storeIndex 
  

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

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

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

I've been assigned to implement a quick sort with a random pivot point (because it's supposedly the most efficient/safest way), yet I've been slaving over a bogosort. Can anyone direct me on how to do it? And can someone help me look at my bogosort to see if I can save it anyway?

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);
    }
}

解决方案

See this pseudocode for inplace patitioning (from 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

Notice it loops through the whole array (except the last index). The pivot isn't swapped until the end. In your code the pivot value keeps changing through the loop which doesn't seem correct.

Each time there is a swap the swap target (storeIndex above) should change.

Also you only need to swap values lower than the pivot to the left. If all the low values are to the left, then the high values will end up on the right.

这篇关于使用Java中的随机数据库快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！