Quicksort не работает как ожидалось

Я пытаюсь реализовать псевдокод CLRS для быстрой сортировки в Java, и я не могу получить массив для сортировки правильно. Код я написал это:Quicksort не работает как ожидалось

private void PrintNumbers(int[] numbers) { 
    for(int number:numbers) { 
     System.out.print(number + " "); 
    } 
    System.out.println(""); 
} 

private void swap(int[] numbers, int i, int j) { 
    int temp; 
    temp = numbers[j]; 
    numbers[j] = numbers[i]; 
    numbers[i] = temp; 
} 


private int Partition(int[] numbers, int start, int end) { 
    int i = start - 1; 
    int wall = numbers[end]; 
    int j; 
    for(j = start; j < end - 1; j++) { 
     if(numbers[j] <= wall) { 
      i++; 
      swap(numbers, i, j); 
     } 
    } 

    swap(numbers, i+1, end); 
    return i+1; 
} 

private void QuickSort(int[] numbers, int start, int end) { 
    if(start < end) { 
     int q = Partition(numbers, start, end); 
     QuickSort(numbers, start, q-1); 
     QuickSort(numbers, q+1, end); 
    } 
} 

public static void main(String[] args) { 
    int[] numbers = {2, 8, 7, 1, 3, 5, 6, 4}; 
    QS qs = new QS(); 
    qs.QuickSort(numbers, 0, numbers.length-1); 
    qs.PrintNumbers(numbers); 
}

выхода я получил для этого кода: 2 3 1 4 5 7 8 6 Любой идея, что я делаю неправильно?

источник

2014-11-10 user3666471

'for (j = start; j

Это, похоже, исправило это. Но теперь я удивляюсь, почему это было «конец-1» в книге. – user3666471

Если это 'end-1', это должно быть' j <= end-1'. Дело здесь в том, что array.length даст вам длину массива, и по мере того, как индекс начинается с нуля, мы обычно делаем 'array.length-1', который даст нам последний индекс. Таким образом, вы уже это делаете, когда вы начинаете 'QuickSort' рекурсивно. –

for(j = start; j < end - 1; j++) должно быть for(j = start; j < end; j++). Другое дело в java, все методы и переменные должны начинаться с строчной буквы, например PrintNumbers, должны быть printNumbers.

Вам не нужно вычитать каждый раз, когда вы это делаете, когда вы вызываете QuickSort в первый раз из основного метода.

источник

2014-11-10 07:09:36

Quicksort не работает как ожидалось

ответ

Смежные вопросы