algorithm
Sortieren durch Einfügen
Suche…
Bemerkungen
Wenn wir die Leistung des Sortieralgorithmus analysieren, interessieren uns in erster Linie die Anzahl der Vergleiche und der Austausch.
Durchschnittlicher Austausch
Sei E n die durchschnittliche Gesamtzahl des Austauschs, um ein Array von N Elementen zu sortieren. E 1 = 0 (wir brauchen keinen Austausch für ein Array mit einem Element). Die durchschnittliche Anzahl der zu wechselnden N-Element-Arrays ist die Summe der durchschnittlichen Anzahl der zu sortierenden N-1-Element-Arrays mit dem durchschnittlichen Austausch zum Einfügen des letzten Elements in das N-1-Element-Array.
Vereinfachung der Summation (arithmetische Reihe)
Erweitert den Begriff
Vereinfachung der Summation noch einmal (arithmetische Reihe)
Durchschnittlicher Vergleich
Sei C n die durchschnittliche Gesamtzahl des Vergleichs zum Sortierfeld des N-Elements. C 1 = 0 (wir brauchen keinen Vergleich in einem Elementarray). Die durchschnittliche Anzahl der Vergleichselemente zum Sortieren von N-Elementen ist die Summe der durchschnittlichen Anzahl der Vergleichszahlen zum Sortieren von N-1-Elementarrays mit dem Durchschnittsvergleich zum Einfügen des letzten Elements in das N-1-Elementarray. Wenn das letzte Element das größte Element ist, benötigen wir nur einen Vergleich. Wenn das letzte Element das zweitkleinste Element ist, benötigen wir einen N-1-Vergleich. Wenn jedoch das letzte Element das kleinste Element ist, benötigen wir keinen N-Vergleich. Wir brauchen nur noch einen N-1-Vergleich. Deshalb entfernen wir 1 / N in der untenstehenden Gleichung.
Vereinfachung der Summation (arithmetische Reihe)
Erweitern Sie den Begriff
Vereinfachen Sie die Summation noch einmal (arithmetische Reihe und harmonische Zahl)
Algorithmus-Grundlagen
Einfügungssortierung ist ein sehr einfacher, stabiler In-Place-Sortieralgorithmus. Bei kleinen Sequenzen funktioniert es gut, bei großen Listen ist es jedoch weniger effizient. Bei jedem Schritt berücksichtigt der Algorithmus das i-te Element der angegebenen Sequenz und bewegt es nach links, bis es sich in der richtigen Position befindet.
Grafische Darstellung
Pseudocode
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
Beispiel
Betrachten Sie die folgende Liste von Ganzzahlen:
[5, 2, 4, 6, 1, 3]
Der Algorithmus führt die folgenden Schritte aus:
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
C # -Implementierung
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
Hilfsraum: O(1)
Zeitkomplexität: O(n)
Haskell-Implementierung
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs