Fügen Sie die Sortierung direkt ein
1 Sortieridee:
Der zu sortierende Datensatz RI wird in die bereits sortierten Datensätze R1, R2, ..., R (N-1) eingefügt.
Für eine zufällige Sequenz, beginnend vom zweiten Element, und das Element in die entsprechende Position im Element einfügen. Die Elemente, bevor es sortiert wurde.
Erste Ordnung: Fügen Sie das zweite Element in die geordnete Liste in der vorhergehenden Reihenfolge ein (zu diesem Zeitpunkt gibt es in der vorherigen nur ein Element, natürlich wird es bestellt). Danach werden die ersten beiden Elemente dieser Sequenz geordnet.
Zweite Sortierung: Fügen Sie das dritte Element in die geordnete Liste der vorherigen Länge 2 ein, damit die ersten beiden Elemente bestellt werden.
Und so weiter, bis das nte Element in die geordnete Liste der vorherigen Länge (N-1) eingefügt wird.
2 Algorithmus -Implementierung:
// SORT SOLLE VOID geraal_insert_sort direkt einfügen (int num [], int len) {int i, j, key; für (j = 1; j <len; j ++) {key = num [j]; i = j-1; while (i> = 0 && num [i]> Schlüssel) {num [i+1] = num [i]; ich--; } num [i+1] = key; }}3 Leistungsanalyse:
3.1 Raumkomplexität: Wie oben erwähnt, wird ein Hilfseinheitschlüssel verwendet, und die Raumkomplexität ist o (1)
3.2 Zeitkomplexität:
3.2.1 Bester Fall: Die zu sortierenden Datensätze sind bereits bestellt und sortieren sie dann in einer Reise, die Schlüsselwörter werden einmal verglichen und die Datensätze werden zweimal verschoben. Der ganze Prozess
Die Anzahl der Vergleiche ist
Die Anzahl der Datenbewegungen ist
Zeitkomplexität O (n)
3.2.2 Schlimmster Fall: Die zu sortierenden Datensätze sind bereits in umgekehrter Reihenfolge, dann sind die Keyword-Vergleichszeiten ich (von I-1 bis 0) und der Datensatz bewegt sich (i+2) Mal. Der ganze Prozess
Die Anzahl der Vergleiche ist
Die Anzahl der Datenbewegungen ist
Zeitkomplexität O (n^2)
3.2.3 Durchschnittliche Zeitkomplexität: O (n^2)
3.3 Stabilität: Stabil
Halbeinfügungssortierung falten
1 Sortieridee:
Basierend auf der direkten Sortierung werden die zu sortierten Datensätze in die bereits sortierten Datensätze R1, R2, ..., R (N-1) eingefügt. Da die Aufzeichnungen R1, R2, ..., R (N-1) sortiert wurden, kann "halbfindend" verwendet werden, wenn nach der Insertionsposition gesucht wird.
2 Algorithmus -Implementierung:
// falten halb sortieren für (i = 1; i <len; i ++) {key = num [i]; niedrig = 0; hoch = i-1; Mid = (niedrig+hoch)/2; // Ermitteln Sie den Insertionspunkt, der endgültige Einfügepunkt ist niedrig, während (niedrig <= hoch) {if (Schlüssel <Mid]) High = Mid-1; sonst niedrig = Mid+1; Mid = (niedrig+hoch)/2; } // Move Record für (j = i; j> low; j-) {num [j] = num [j-1]; } // Datensatz num [niedrig] = Schlüssel einfügen; }}3 Leistungsanalyse:
3.1 Raumkomplexität: Wie oben erwähnt, wird ein Hilfseinheitschlüssel verwendet, und die Raumkomplexität ist o (1)
3.2 Zeitkomplexität: Obwohl die halbfinische Suche die Anzahl der Datensätze und Vergleiche reduziert, verringert sie die Anzahl der Bewegungen nicht, sodass die Zeitkomplexität dem direkten Suchalgorithmus übereinstimmt.
3.2.1 Bester Fall: Zeitkomplexität O (n)
3.2.2 Schlimmster Fall: Zeitkomplexität O (n^2)
3.2.3 Durchschnittliche Zeitkomplexität: O (n^2)
3.3 Stabilität: Stabil