Schnellsortieren besteht darin, ein Element (ursprünglich Sie eines finden) als Referenz (Drehzahl) zu finden und dann das Array zu verteilnen, damit der Wert des Elements links von der Referenz nicht größer ist als der Referenzwert und der Wert Das Element rechts von der Referenz ist nicht geringer als der Referenzwert. Rekursiv schnelle Sortierung, passen Sie die anderen N-1-Elemente nach der Sortierung an die richtige Position an. Schließlich befindet sich jedes Element nach der Sortierung in der richtigen Position und die Sortierung ist abgeschlossen. Daher ist der Kernalgorithmus des Schnellsortieralgorithmus die Partitionierungsoperation, dh wie die Position des Benchmarks und die Anpassung der endgültigen Position des Rückgabemarks anpassen, um die Rekursion zu teilen und zu erobern.
Der Algorithmus für die schnelle Sortierung lautet:
1) Stellen Sie zwei Variablen I und J fest, wenn die Sortierung beginnt: i = 0, j = n-1;
2) Verwenden Sie das erste Array -Element als Schlüsseldaten und weisen Sie es dem Schlüssel zu, dh Key = a [0];
3) Beginnen Sie von J, um nach vorne zu suchen, dh von hinten zu suchen, um nach vorne zu suchen (j-), finden Sie den ersten Wert A [j] kleiner als Schlüssel und tauschen Sie A [j] und A [i] aus;
4) Beginnen Sie von mir nach rückwärts, dh von vorne nach hinten (i ++), finden Sie die ersten A [i] größer als der Schlüssel und tauschen Sie A [i] und A [j] aus;
5) Wiederholen Sie die Schritte 3 und 4 bis i = j; 4 ist nicht größer als Schlüssel ändern die Werte von J und I, damit J = J-1, i = i+1, bis es gefunden wird. bleibt unverändert.
Lassen Sie mich Ihnen ein Beispiel geben, dies ist möglicherweise nicht leicht zu verstehen. Angenommen, die zu sortierte Sequenz ist
Die Codekopie lautet wie folgt:
Paket com.zc.manythread;
import Java.util.random;
/**
* Schnelle Sortierung
* @Author Administrator
*
*/
öffentliche Klasse QSORT {
int [] Datum;
public QSORT (int [] Datum) {
this.date = Datum;
}
/**
* Austauschfunktion
* @param a
* @param i
* @param j
*/
privater void Swap (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/*****************************
* Sortierfunktion
* @param a
* @param lo0
* @param hi0
* @zurückkehren
*/
Int [] Quicksort (int a [], int lo0, int hi0) {// Die Methode der Aufteilung und Behandlung besteht darin, das Array in ein [lo0..q-1] und ein [q+1..hi0] zu unterteilen.
int lo = lo0;
int hi = hi0;
int in Mid;
if (hi0> lo0) {
Mid = a [(Hi0+lo0)/2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hi> lo0) && (a [hi]> mid) - -hi;
if (lo <= hi) {
tauschen (a, lo, hi);
++ lo;
--Hi;
}
}
if (lo0 <hi) {
Quicksort (a, lo0, hi);
}
if (lo <hi0) {
Quicksort (a, lo, hi0);
}
}
Rückkehr a;
}
/******************
*
* Erstellen Sie doppelte Array -Daten
********************//
private static int [] createdate (int count) {
int [] data = new int [count];
für (int i = 0; i <data.length; i ++) {
Daten [i] = (int) (math.random ()*count);
}
Daten zurückgeben;
}
/**
* Keine doppelten Array -Daten
* @param count
* @zurückkehren
*/
private static int [] createdate1 (int count) {
int [] data = new int [count];
Random rand = new random ();
boolean [] bool = neuer boolean [100];
int num = 0;
für (int i = 0; i <count; i ++) {
Tun {
// Wenn die generierte Zahl gleich ist, werden Sie fortgesetzt, um weiter zu schleifen
Num = Rand.Nextint (100);
} while (bool [num]);
bool [num] = true;
Daten [i] = num;
}
Daten zurückgeben;
}
/************************************
public static void main (String [] args) {
endgültige int count = 10;
int [] data = createdate1 (count);
für (int n: data) {
System.out.print (n+"/t");
}
QSORT Data1 = New QSORT (Daten);
System.out.println ();
int [] a = data1.quicksort (Daten, 0, count-1);
für (int n: a) {
System.out.print (n+"/t");
}
}
}
Die Ergebnisse sind wie folgt:
Das obige Inhalt ist in diesem Artikel. Ich hoffe, Sie können es mögen.