Die Sortiereffizienz wird im Allgemeinen anhand von drei Aspekten verglichen: der Anzahl der Datenvergleiche, der Anzahl der Datenverschiebungen und der Menge des belegten Speicherplatzes.
Lassen Sie uns einen allgemeinen Vergleich zwischen Blasensortierung, Auswahlsortierung, Einfügungssortierung und Schnellsortierung durchführen. Der Blasensortierungsalgorithmus wird im Allgemeinen nicht verwendet, da er unter mehreren Sortieralgorithmen die größte Anzahl an Vergleichen und Verschiebungen aufweist. Sein einziger Vorteil besteht darin, dass der Algorithmus einfach und leicht zu verstehen ist und daher verwendet werden kann, wenn die Datenmenge gering ist wird ein gewisser Anwendungswert sein. Die Auswahlsortierung hat die gleiche Anzahl an Vergleichen wie die Blasensortierung, die n im Quadrat ist, reduziert jedoch die Anzahl der Austausche auf ein Minimum, sodass sie angewendet werden kann, wenn die Datenmenge klein ist und der Datenaustausch zeitaufwändiger ist als der Vergleich Daten auswählen.
In den meisten Fällen ist der Einfügungssortierungsalgorithmus die beste Wahl, wenn die Datenmenge relativ klein oder grundsätzlich geordnet ist. Zum Sortieren größerer Datenmengen ist Quicksort normalerweise die beste Methode.
Der obige Sortieralgorithmus benötigt sehr wenig Speicherplatz und erfordert lediglich eine zusätzliche Variable, um die Datenelemente während des Austauschs vorübergehend zu speichern. Daher gibt es keinen Vergleich hinsichtlich der Größe des belegten Speicherplatzes.
Die Anzahl der Vergleiche bei der Einfügungssortierung beträgt immer noch n im Quadrat, ist aber im Allgemeinen doppelt so schnell wie die Blasensortierung und etwas schneller als die Auswahlsortierung. Es wird häufig in der Endphase komplexer Sortieralgorithmen wie Quicksort verwendet.
Algorithmus: Nach der i-1-Verarbeitung wurde L[1..i-1] sortiert. Der i-te Durchgang fügt L[i] nur an der entsprechenden Position von L[1..i-1] ein,
Damit ist L[1..i] wieder eine geordnete Folge. Um dieses Ziel zu erreichen, können wir einen sequentiellen Vergleich verwenden.
Vergleichen Sie zuerst L[i] und L[i-1]. Wenn L[i-1]<=L[i], dann wurde L[1..i] sortiert und der i-te Verarbeitungsdurchlauf ist beendet;
Andernfalls tauschen Sie die Positionen von L[i] und L[i-1] aus und vergleichen Sie L[i-1] und L[i-2] weiter, bis eine bestimmte Position j (1 ≤ j ≤ i-1) erreicht ist gefunden.
Bis L[j] ≤L[j+1]
Vorteile: Es werden weniger Elemente bewegt und es wird nur ein Nebenraum benötigt
Zeitkomplexität n*n
Dies ist eine gute Sortiermethode, wenn die Anzahl n der zu sortierenden Datensätze klein ist. Wenn n jedoch sehr groß ist, ist dies ungeeignet
Zum Beispiel: int[] value = { 5, 2, 4, 1, 3 };
Sortiervorgang:
1. Mal: 2,5,4,1,3
2. Mal: 2,4,5,1,3
3. Mal: 1,2,4,5,3
4. Mal: 1,2,3,4,5
Java-Code:
Kopieren Sie den Codecode wie folgt:
öffentliche Klasse InsertSort {
public static void main(String[] args) {
int[] Werte = { 5, 2, 4, 1, 3 };
sort(werte);
for (int i = 0; i < Werte.Länge; ++i) {
System.out.println(values[i]);
}
}
public static void sort(int[] Values) {
int temp;
int j = 0;
for (int i = 1; i < Werte.Länge; i++) {
if(values[i]<values[i-1])//Die Beurteilung hier ist sehr wichtig. Dies spiegelt den Grund wider, warum die Einfügungssortierung schneller ist als die Blasensortierung und die Auswahlsortierung.
{
temp = Werte[i];
//Daten rückwärts verschieben
for (j=i-1; j>=0 && temp<values[j]; j--)
{
Werte[j+1] =Werte[j];
}
//Daten an Position j+1 einfügen
Werte[j+1] =temp;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k < Werte.Länge; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
Zweites Beispiel
Kopieren Sie den Codecode wie folgt:
Paket cn.cqu.coce.xutao;
öffentliche Klasse Zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
if(a[i]>a[j])
brechen;
if(j!=i-1){
int temp;
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=temp;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}