Алгоритм разбиения QuickSort

Question

Я пытаюсь запрограммировать алгоритм быстрой сортировки из учебника по алгоритму Кормена.Ниже приведен мой код.

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 

Может кто-нибудь объяснить, пожалуйста, что не так.Я реализовал этот код именно так, как указано в книге «Введение в алгоритмы».Спасибо.

Answer 1

Нет, вы не скопировали его напрямую :) У меня оно есть здесь ...

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

Answer 2

Предоставление еще одной реализации в Java.Он также основан на том же алгоритме и учитывает дубликаты элементов в массиве.

    public void sort( int[] inputArray, int lo, int high){
          int pivotIndex = partition(inputArray,lo,high);
         System. out .println("Got PivotIndex as " + pivotIndex);
          if (lo < pivotIndex -1)
                sort(inputArray,lo,pivotIndex - 1);
          if (pivotIndex+1 < high)
                sort(inputArray,pivotIndex+1,high);
          return ;
    }

    private int partition( int[] inputArray, int leftPtr,int rightPtr)
   {
         printArray(inputArray);
          int pivot = inputArray[leftPtr];
          while (leftPtr<rightPtr){
                 while (inputArray[leftPtr]<pivot)
                       leftPtr++;
                 while (inputArray[rightPtr]>pivot)
                       rightPtr--;
                 if (leftPtr<rightPtr)
                {
                       exchange(inputArray,leftPtr,rightPtr);

                          //Cases which have repeated numbers...
                        if (inputArray[leftPtr] == inputArray[rightPtr])
                             leftPtr++;
                }
         }
          return leftPtr;//return any one
   }

Answer 3

Если вам нужна информация о том, как реализовать быструю сортировку, вы можете попробовать проверить фактический исходный код Arrays.sort (*) в jdk, который является модифицированной версией быстрой сортировки.(http://www.oracle.com/technetwork/java/javase/downloads/index.html для загрузки, если у вас еще нет src.zip в вашей установке jdk).