Я пытаюсь реализовать программу алгоритма 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
Кто-либо мог сказать мне, как я могу получить свой результат требования?
Проблема в том, что на самом деле quicksort работает не так. Quicksort - это рекурсивный алгоритм, который должен вызываться только один раз извне. Идея заключается в том, что на каждой итерации вы разбиваете массив на две половины - левая половина содержит все элементы меньше, чем ось, а правая - все элементы больше/равнее оси. Затем вы сортируете две половинки и, наконец, помещаете ось посередине.
Если длина стороны, на которой выполняется зыбучие сортировки, меньше 3 элементов, можно просто поменять местами эти два элемента или оставить их, и эта часть массива будет выполнена.
Но не похоже, что ваш код делает это вообще - вы вызываете Quicksort 6 раз от своего клиента, а внутри функции quicksort
вы делаете максимум один swap. Таким образом, это не тот случай, когда кто-то сможет посмотреть на ваш код и отладить его, сказав вам переместить своп или что-то в этом роде. Вам нужно пересмотреть свою логику.
Посмотрите на диаграмму Википедии для визуального примера того, что должно произойти в одной итерации:
Существуют реализации быстрой сортировки с открытым исходным кодом в Apache Harmony и Apache Mahout, вероятно, среди многих других. Вы можете их прочитать.
Полный рабочий код для алгоритма быстрой сортировки, реализованного на Java, можно найти здесь