Die schnelle Sortierung hat mich lange beschäftigt und gequält, weil ich die allgemeine Idee habe, aber beim Schreiben von Code treten immer noch verschiedene Probleme auf. Es ist für mich persönlich immer noch schwierig Ein gewisser Schwierigkeitsgrad, und aufgrund von Arbeit und Faulheit wurden die Fehler, die nicht behoben werden konnten, schon lange weggeräumt. Heute ist es endlich raus und ich bin immer noch ein wenig aufgeregt eine kleine Erklärung.
Um das schnelle Sortieren zu erlernen, müssen Sie zunächst die Methode „Teile und herrsche“ erlernen. Die Idee von „Teile und herrsche“ besteht darin, eine Folge von Zahlen außerhalb der Reihenfolge anzugeben (die Zahlen sind Annahmen, sie können auch andere Objekte sein). Natürlich können Sie die Parameter der Methode selbst definieren (Angenommen, es gibt ein Array von Ganzzahlen) und es ihm dann geben Eine mittlere Zahl, die Methode „Teilen und Erobern“, teilt diese Zahlen basierend auf der ihr zugewiesenen mittleren Zahl in zwei Teile, wobei sich ein Teil links von der mittleren Zahl und der andere Teil rechts davon befindet Trennpunkt, die Zahlen auf beiden Seiten sind immer noch nicht in Ordnung. Ich habe es wie folgt definiert:
//left ist der linke Endpunkt des Divide-and-Conquer-Teils des Arrays und right ist der gesamte Endpunkt des Divide-and-Conquer-Teils des Arrays. Beispielsweise für ein Array mit einer Länge von 10, wenn Ich möchte die ersten 5 ganzen Zahlen dividieren und erobern, ich kann 0 oder 4 als öffentliches int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> übergeben n-1){ return -1; } int temp = test[left]; j=right; int i=left; while(test[j]>=test[left]&&i<j){ j--; &&i<j){ i++ } if(i<j){ temp = test[i]; test[i]=test[j] } } if(i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" " } return i ; }Natürlich können Sie auch die mittlere Zahl als Parameter übergeben. Jetzt verwende ich nur die übergebene linke Zahl als Teilungszahl.
Nachdem Sie das Teilen und Erobern verstanden haben, ist das schnelle Sortieren einfach. Das heißt, die Zahlen, die geteilt wurden, werden in zwei Teile geteilt und so weiter, bis alle Zahlen in der richtigen Reihenfolge sind.
public void quickSort(int left,int right){ if(right-left<1){ return }else{ int point = this.signalFenZhi(left, right); //if( point!=left&&point!=right){ quickSort(left,point-1); quickSort(point+1,right) } }Die Effizienz der Schnellsortierung ist unter vielen Sortieralgorithmen hervorragend. Die Zeitkomplexität beträgt O(N*log2n). Wenn der Teilungspunkt von Teilen und Erobern jedoch nicht gut gewählt wird, wird die Zeitkomplexität auf (n im Quadrat) reduziert. ), denn wenn dieses Array zufällig sortiert wird und wir dann jedes Mal die am weitesten links übergebene Zahl verwenden, ist die Effizienz sehr gering, sodass wir diese Situation vermeiden müssen. Wenn alle Optionen getestet werden, wird dies sehr lange dauern Zeit, also Eine Kompromissmethode besteht darin, eine mittlere Zahl zur Zahl ganz links und zur Zahl ganz rechts zu addieren und die mittlere Zahl zwischen ihnen zu finden. Basierend auf der obigen Methode sieht der geänderte Code wie folgt aus: Aber nachdem ich es beendet hatte, war dieser Ansatz nicht sehr gut. Es wäre besser, den Teilungswert als Methode des Teilens und Eroberns weiterzugeben, aber ich werde es hier nicht versuchen.
package com.jll; public class FenZhi { int[] test; public FenZhi(){ test = new int[10]; =(int)(Math.random()*100)+1; System.out.print(test[i]+" " } System.out.println(); n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random ()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1; } if(right-left>=2){ int middle = (rechts+links)/2; if(test[left]>test[middle]){ int temp = test[middle]; if(test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; test[right] = temp; ){ int temp = test[middle]; test[middle] = test[right]; test[right] = temp } int temp = test[middle]; = temp; int j=right-1; int i=left+1; while(test[j]>=test[left]&&i<j){ j--; ]<=test[left]&&i<j){ i++ } if(i<j){ temp = test[i]; test[j]=temp; i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp } /*if(i==j){ temp = test[middle]=test[i ]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" }*/ return i; anders { if(test[right]<test[left]){ int temp = test[right]; test[right] = test[left]; test[left] = temp ,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right); System.out.println("the point ist: "+point); quickSortMajorizationFirst(left,point-1); quickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ System.out.print(i+" "); }}Der Code läuft wie folgt ab:
95 40 64 18 78 23 73 84 40 Der Punkt ist:4Der Punkt ist:1Der Punkt ist:3Der Punkt ist:7Der Punkt ist:6Der Punkt ist:918 23 40 40 64 73 78 84 95
Das Obige ist das, was ich gelernt habe. Notieren Sie es zum späteren Nachschlagen.