Я пытаюсь программировать quicksort алгоритм из Учебника Алгоритма Cormen. Ниже мой код.
class Quicksort
{
public void qSort(int[] a, int p, int r)
{
if(p<r)
{
int q = Partition(a, p,r);
qSort(a, p, q-1);
qSort(a, q+1, r);
}
}
private int Partition(int[] a, int p, int r)
{
int x = a[r];
int i = p-1;
int temp=0;
for(int j=p; j<r-1; j++)
{
if(a[j]<=x)
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
}
public class QuickSortTest
{
public static void main(String[] args)
{
Quicksort qsort = new Quicksort();
int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};
System.out.print("Original Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
int length = array.length;
qsort.qSort(array, 0, length-1);
System.out.print("Sorted Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
}
}
Но, я получаю неправильный вывод, когда я выполняю этот код.
Original Array : 5 4 7 2 1 9 3 6 10 8
Sorted Array : 1 4 5 2 6 7 3 8 9 10
Может любой объяснять что не так. Я реализовал этот код точно, как дали во "Введении в алгоритмы" книга.Спасибо.
Нет, вы не копировали его напрямую :) Он у меня здесь ...
for(int j=p; j<r-1; j++)
должен быть
for(int j=p; j<r; j++)
или
for(int j=p; j <= r-1; j++)
В книге написано:
for j = p to r - 1
который включает r - 1
. И помните, что в книге есть массивы, которые начинаются с 1, а не с 0. Так что обычно алгоритмы в книге следует «копировать» с большой осторожностью или с массивами, начинающимися с 1.
Редактировать: Информация об алгоритме для комментария Алгоритм в книге принимает последний элемент в качестве стержня. Следовательно, это сделает его ужасным алгоритмом для уже отсортированных массивов. Он закончится O (n ^ 2), поэтому никто не должен использовать этот алгоритм в производстве (если вы не знаете, что делаете и каков ваш ввод), поскольку массивы, как правило, несколько отсортированы. Встроенный алгоритм Java более умен, и вы можете прочитать об этом в Javadoc
Если вам нужна справка о том, как реализовать быструю сортировку, вы можете попробовать проверить фактический исходный код для Arrays.sort (*) в jdk, который представляет собой модифицированную версию быстрой сортировки. ( http://www.oracle.com/technetwork/java/javase/downloads/index.html для загрузки, если у вас еще нет src.zip в вашей установке jdk).