Quicksort-Algorithmus-Programm in Java

Question

Ich versuche, QuickSort-Algorithmus-Programm in Java zu implementieren, aber ich bekomme falsche Antwort.

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

} 

Das obige Programm mir die Ausgabe als geben: 12 23 22 33 34 33 64 34 64

Könnte jemand bitte sagen Sie mir, wie kann ich meinen Wunsch Ergebnis bekommen?

Answer 1

Das Problem ist, dass dies nicht wirklich funktioniert, wie Quicksort funktioniert. Quicksort ist ein rekursiver Algorithmus, der nur einmal von außerhalb aufgerufen werden sollte. Die Idee besteht darin, dass Sie das Array bei jeder Iteration in zwei Hälften teilen - die linke Hälfte enthält alle Elemente, die kleiner als der Drehpunkt sind, und die rechte Hälfte enthält alle Elemente, die größer/gleich dem Drehpunkt sind. Dann schnellst du die beiden Hälften und legst den Drehpunkt in die Mitte.

Wenn die Seite, die Sie Quicksorting sind weniger als 3 Elemente lang ist, können Sie einfach die beiden Elemente tauschen oder lassen, und dieser Teil des Arrays ist fertig.

Aber es sieht nicht so aus, als würde Ihr Code das überhaupt tun - Sie rufen Quicksort 6-mal von Ihrem Client an und innerhalb der quicksort Funktion machen Sie höchstens einen Tausch. Das ist also kein Fall, in dem jemand Ihren Code ansehen und debuggen kann, indem er Ihnen sagt, dass Sie einen Swap oder etwas verschieben sollen. Sie müssen Ihre Logik erneut aufsuchen.

Check out Wikipedia Diagramm für ein visuelles Beispiel dafür, was sollte in einer einzigen Iteration geschehen:

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

Answer 2

Es gibt Open-Source-Implementierungen von quicksort in Apache Harmony und Apache Mahout, wahrscheinlich unter vielen Andere. Sie können sie lesen.

Answer 3

Bitte umfassenden Arbeitscode für schnellen Sortier-Algorithmus in Java implementiert hier finden,

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

Answer 4

Ihre Schleife nicht richtig funktioniert. den Code finden, die Ihr Problem über Quick Sort

mit einer Beschreibung [Code bei nathan's computer knowledge mit Beschreibung verfügbar ist lösen

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

Siehe 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

hier ist ein quicksort Algorithmus

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

auch ] [/ code] ``