Блог

Главная - Вопросы по программированию - Алгоритм быстрой сортировки Java

Алгоритм быстрой сортировки Java

#java #algorithm #sorting #quicksort

#java #алгоритм #сортировка #быстрая сортировка

Вопрос:

Я пытаюсь изучить алгоритм быстрой сортировки, и пока это мой код:

 import java.util.Arrays;

public class JavaFiddle {
    static int[] myArray = new int[]{35, 12, 25, 1, 5, 33, 56};

    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }

    public static void QuickSort(int[] array, int left, int right) {
        if (left < right) {
            int pivot = left   ((right - left) / 2);
            int index = partition(array, left, right, pivot);
            QuickSort(array, left, index - 1);
            QuickSort(array, index   1, right);
        }
    }

    public static int partition(int[] array, int left, int right, int pivot) {
        while (left < right) {
            while (array[left] < pivot) {
                left  ;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left < right) {
                swap(array, left, right);
                left  ;
                right--;
            }
        }
        return left;
    }

    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

Однако этот код дает мне неверный результат:

 [35, 12, 25, 1, 5, 33, 56] - before sort
[1, 12, 25, 35, 5, 33, 56] - after sort

Что у меня здесь не так? Я не могу найти недостаток в логике.

Комментарии:

1. Вы пробовали добавлять println в начале QuickSort , чтобы вывести подмассив между left и right , чтобы вы могли точно узнать, когда произойдет что-то неожиданное?

2. @Stef Никто не сказал что-то еще. По-прежнему важно информировать людей о недостатках в их общении. Одна из составляющих становления программистом… принять: все детали имеют значение.

3. Я осознал свою ошибку и отредактировал сообщение. Да, программа компилируется без каких-либо ошибок, и я обнаружил, что она сортирует только левую часть массива, а не правую часть, если это поможет вам понять проблему.

Ответ №1:

Здесь несколько ошибок,
вы определяете pivot в основном методе, но алгоритм быстрой сортировки поменяет pivot с правого элемента на средний. Вы редактируете значения left и right в своем цикле while в цикле while, в результате чего right и left становятся меньше / выше вашего pivot и пропускают некоторые замены.
Вот правильная реализация без вашего while { while { ... } } и правильного поворота (справа на середину)

 import java.util.Arrays;
public class Main
{
    static int[] myArray = new int[] {35, 12, 25, 1, 5, 56, 33};
    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }
    public static void QuickSort(int[] array, int left, int right){
        if(left < right) {
            int index = partition(array, left, right);
            QuickSort(array, left, index - 1);
            QuickSort(array, index   1, right);
        }
    }
    public static int partition(int[] array, int left, int right){
        int pivot = array[right];
        int first = left - 1;
        for (int j = left; j <= right - 1; j  ) {
            if(array[j] < pivot) {
                first   ;
                swap(array, first, j);
            }
        }
        swap(array, first   1, right);
        return first   1;
    }
    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

Также вы сравниваете, pivot который является индексом, с array[...] который является значением