Быстрый алгоритм разбиения на разделы

Question

Я пытаюсь запрограммировать алгоритм быстрой сортировки из Cormen Algorithm Textbook. Ниже мой код.

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

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

Answer 3

Предоставление еще одной реализации в 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 
    }