Die Schnellsortierung wird häufig als effizienter Sortieralgorithmus verwendet. Die Arrays.sort-Methode im JDK von SUN verwendet die Schnellsortierung.
Quick Sort übernimmt die klassische Divide-and-Conquer-Idee:
Teilen: Wählen Sie ein Grundelement X aus (normalerweise das erste Element des Arrays) und teilen Sie das Array durch eine Partitionierungsoperation in zwei Teile: Die linke Hälfte ist kleiner oder gleich X und die rechte Hälfte ist größer oder gleich X .
Erobern: Das linke und das rechte Subarray rufen den Divide-Prozess rekursiv auf.
Kombinieren: Die Schnellsortierung wird als direkter Sortieralgorithmus verwendet und erfordert keine Zusammenführungsvorgänge.
Es ist ersichtlich, dass der Kernbestandteil der Schnellsortierung der Partitionierungsprozess ist. Im Folgenden finden Sie ein Beispiel, um die Partitionierung des Arrays im Detail zu erläutern (Bild aus „Einführung in Algorithmen“).
Initialisierung: Wählen Sie das Grundelement P=2 aus, das das erste Element des Arrays ist. i=1,j=i+1=2 (Array-Index beginnt mit 1)
Schleifeninvariante: Die Elemente zwischen 2~i sind alle kleiner oder gleich P, und die Elemente zwischen i+1~j sind alle größer oder gleich P.
Schleifenprozess: j geht von 2 nach n, untersucht das Element an Position j und setzt die Schleife fort, wenn es größer oder gleich P ist. Wenn es kleiner als P ist, tauschen Sie die Elemente an Position j (die nicht im Bereich i+1~j erscheinen sollten) mit den Elementen an Position i+1 (immer noch im Bereich i+1~j nach dem Austausch) aus. und gleichzeitig i+1 ändern. Dadurch bleiben Schleifeninvarianten erhalten (siehe die Beschreibung der Schleifeninvarianten oben). Bis j = n ist die letzte Schleifenoperation abgeschlossen.
Es ist zu beachten, dass nach Abschluss der Schleife das Element an Position i mit dem ersten Element des Arrays ausgetauscht werden muss, um die von uns zuerst festgelegten Anforderungen zu erfüllen (entsprechend dem i-ten Schritt in der Abbildung).
Aufmerksame Leser können sich eine andere, einfachere Partitionierungsmethode vorstellen, nämlich das Herausnehmen der Grundelemente und deren Speicherung in einem anderen Array derselben Größe. Wenn sie auf Elemente stoßen, die kleiner als die Grundelemente sind, werden sie in der linken Hälfte des Arrays gespeichert Elemente, die größer als die Grundelemente sind, werden in der linken Hälfte des Arrays gespeichert. Die Elemente werden in der rechten Hälfte des Arrays gespeichert. Die Komplexität solcher Operationen ist ebenfalls linear, nämlich Theta(n). Aber die räumliche Komplexität verdoppelt sich. Dies ist auch der Vorteil der schnellen Sortierung vor Ort.
Kopieren Sie den Codecode wie folgt:
öffentliche Klasse QuickSort {
private static void QuickSort(int[] array,int start,int end)
{
if(start<end)
{
int key=array[start];//Grundelemente initialisieren und speichern
int i=start,j;// i,j initialisieren
for(j=start+1;j<=end;j++)
if(array[j]<key)//Wenn das Element hier kleiner als das Grundelement ist, tauschen Sie dieses Element mit dem Element bei i+1 aus und addieren Sie 1 zu i. Wenn es größer oder gleich dem Grundelement ist, fahren Sie fort die Schleife.
{
int temp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
i++;
}
}
array[start]=array[i];//Elemente und Grundelemente bei i austauschen
array[i]=key;
QuickSort(array, start, i-1);//rekursiver Aufruf
QuickSort(array, i+1, end);
}
}
public static void main(String[] args)
{
int[] array=new int[]{11,213,134,44,77,78,23,43};
QuickSort(array, 0, array.length-1);
for(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}