Быстрая сортировка со случайным поворотом в Java

Question

Мне поручили осуществить быструю сортировку со случайной точкой поворота (потому что это, предположительно, самый эффективный / самый безопасный способ), но я работал над 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 выше) должна меняться.

Также вам нужно толькопоменять местами значения ниже, чем шарнир влево.Если все низкие значения находятся слева, то высокие значения окажутся справа.