Программа алгоритма Quicksort в Java

Я пытаюсь реализовать программу алгоритма QuickSort в Java, но я получаю неправильный ответ.

public class QuickSort {

    public static void main(String[] args){
        int arr[]={12,34,22,64,34,33,23,64,33};
        int i=0;
        int j=arr.length;
        while(i<j){
            i=quickSort(arr,i,i+1,j-1);

        }   
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }

    public static int quickSort(int arr[],int pivot,int i,int j){

        if(i>j) {           
            swap(arr,pivot,j);
            return i;
        }

        while(i<arr.length&&arr[i]<=arr[pivot]) {
            i++;
        }

        while(j>=1&&arr[j]>=arr[pivot]) {           
            j--;
        }   
        if(i<j)
            swap(arr,i,j);

        return quickSort(arr,pivot,i,j);

    }   
    public static void swap(int[] arr,int i,int j) {
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}

Вышеупомянутая программа, дающая мне вывод как: 12 23 22 33 34 33 64 34 64

Кто-либо мог сказать мне, как я могу получить свой результат требования?

6
задан ROMANIA_engineer 20 November 2014 в 21:07
поделиться

3 ответа

Проблема в том, что на самом деле quicksort работает не так. Quicksort - это рекурсивный алгоритм, который должен вызываться только один раз извне. Идея заключается в том, что на каждой итерации вы разбиваете массив на две половины - левая половина содержит все элементы меньше, чем ось, а правая - все элементы больше/равнее оси. Затем вы сортируете две половинки и, наконец, помещаете ось посередине.

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

Но не похоже, что ваш код делает это вообще - вы вызываете Quicksort 6 раз от своего клиента, а внутри функции quicksort вы делаете максимум один swap. Таким образом, это не тот случай, когда кто-то сможет посмотреть на ваш код и отладить его, сказав вам переместить своп или что-то в этом роде. Вам нужно пересмотреть свою логику.

Посмотрите на диаграмму Википедии для визуального примера того, что должно произойти в одной итерации:

http://en.wikipedia.org/wiki/File:Partition_example.svg

12
ответ дан 8 December 2019 в 18:36
поделиться

Существуют реализации быстрой сортировки с открытым исходным кодом в Apache Harmony и Apache Mahout, вероятно, среди многих других. Вы можете их прочитать.

1
ответ дан 8 December 2019 в 18:36
поделиться

Полный рабочий код для алгоритма быстрой сортировки, реализованного на Java, можно найти здесь

http://tech.bragboy.com/2010/01/quick-sort-in-java.html

0
ответ дан 8 December 2019 в 18:36
поделиться
Другие вопросы по тегам:

Похожие вопросы: