使用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]){ //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; lowtarget[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）都应该改变。

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