Program algorytmu Quicksort w Javie

Question

Próbuję zaimplementować program algorytmów QuickSort w Javie, ale otrzymuję niepoprawną odpowiedź.

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; 
    } 

} 

Powyższy program daje mi wyjście jako: 12 23 22 33 34 33 64 34 64

Czy ktoś może mi powiedzieć jak mogę dostać rezultat pożądania?

Answer 1

Problem polega na tym, że tak naprawdę nie działa Quicksort. Quicksort jest rekursywnym algorytmem, który powinien być wywoływany tylko raz z zewnątrz. Chodzi o to, że przy każdej iteracji dzielisz tablicę na dwie połówki - lewa połowa zawiera wszystkie elementy mniejsze niż oś obrotu, a prawa połowa zawiera wszystkie elementy większe niż/równe osi obrotu. Następnie szybko obie połówki, a na końcu umieścić czop w środku.

Jeśli strona, którą szybko otwierasz ma mniej niż 3 elementy, możesz po prostu zamienić dwa elementy lub je opuścić, a ta część tablicy zostanie wykonana.

Ale to nie wygląda na to, że Twój kod w ogóle to robi - dzwonisz do Quicksorta 6 razy od swojego klienta, aw ramach funkcji quicksort robisz co najwyżej jedną zamianę. Więc nie jest tak, że ktoś będzie mógł spojrzeć na twój kod i debugować go, mówiąc, aby przesunąć wymianę lub coś takiego. Musisz powrócić do swojej logiki.

Sprawdź schemacie Wikipedia dla wizualnego przykład tego, co ma się stać w jednej iteracji:

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

Answer 2

Istnieją implementacje open source z quicksort w Apache Harmony i Apache Kornak, prawdopodobnie wśród wielu inni. Możesz je przeczytać.

Answer 3

Proszę znaleźć kompleksowe kod pracy dla szybkiego algorytmu sortowania realizowanego w Javie Tutaj

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

Answer 4

Twój pętli nie działa prawidłowo. Patrz kod, który ma rozwiązać problem o Quick Sort

static void quickSort (int[] numbers, int low, int high) 
{ 
    int i=low; 
    int j=high; 
    int temp; 
    int middle=numbers[(low+high)/2]; 

    while (i<j) { 

     while (numbers[i]<middle) { 
      i++; 
     } 

     while (numbers[j]>middle) { 
      j--; 
     } 

     if (i<=j) { 
      temp=numbers[i]; 
      numbers[i]=numbers[j]; 
      numbers[j]=temp; 
      i++; 
      j--; 
     } 
    } 

    if (low<j) { 
     quickSort(numbers, low, j); 
    } 

    if (i<high) { 
     quickSort(numbers, i, high); 
    } 
} 

odnoszą Quick sort.

Answer 5

public static int partition(int[] a, int p, int r){ 

     int i=p,j=r,pivot=a[r]; 

     while(i<j){ 

      while(i<r && a[i] <= pivot){ 
       i++; 
      } 

      while(j>p && a[j]>pivot){ 
       j--; 
      } 

      if(i<j){ 
       swap(a, i, j); 
      }   
     } 
     return j; 
    } 

    public static void quickSort(int[] a, int p, int r){ 
     if(p<r){ 
      int q=partition(a, p, r); 

      if(p==q){ 
       quickSort(a, p+1, r); 
      }else if(q==r){ 
       quickSort(a, p, r-1); 
      }else { 
       quickSort(a, p, q); 
       quickSort(a, q+1, r); 
      } 

     } 
    } 

    public static void swap(int[] a, int p1, int p2){ 
     int temp=a[p1]; 
     a[p1]=a[p2]; 
     a[p2]=temp; 
    } 

Answer 6

Oto algorytm Quicksort

package drawFramePackage; 
    import java.awt.geom.AffineTransform; 
    import java.util.ArrayList; 
    import java.util.ListIterator; 
    import java.util.Random; 
    public class QuicksortAlgorithm { 
     ArrayList<AffineTransform> affs; 
     ListIterator<AffineTransform> li; 
     Integer count, count2; 
     /** 
     * @param args 
     */ 
     public static void main(String[] args) { 
      new QuicksortAlgorithm(); 
     } 
     public QuicksortAlgorithm(){ 
      count = new Integer(0); 
      count2 = new Integer(1); 
      affs = new ArrayList<AffineTransform>(); 
      for (int i = 0; i <= 128; i++){ 
       affs.add(new AffineTransform(1, 0, 0, 1, new Random().nextInt(1024), 0)); 
      } 
      affs = arrangeNumbers(affs); 
      printNumbers(); 
     } 
     public ArrayList<AffineTransform> arrangeNumbers(ArrayList<AffineTransform> list){ 
      while (list.size() > 1 && count != list.size() - 1){ 
       if (list.get(count2).getTranslateX() > list.get(count).getTranslateX()){ 
        list.add(count, list.get(count2)); 
        list.remove(count2 + 1); 
       } 
       if (count2 == list.size() - 1){ 
        count++; 
        count2 = count + 1; 
       } 
       else{ 
       count2++; 
       } 
      } 
      return list; 
     } 
     public void printNumbers(){ 
      li = affs.listIterator(); 
      while (li.hasNext()){ 
       System.out.println(li.next()); 
      } 
     } 
    } 

również dostępny z opis na nathan's computer knowledge z opisem [code ] [/ code] ``