algorithm
Insättningssortering
Sök…
Anmärkningar
När vi analyserar prestanda för sorteringsalgoritmen, intresserar vi främst antalet jämförelser och utbyten.
Genomsnittligt utbyte
Låt E n vara det totala genomsnittliga antalet utbyten för att sortera array av N-element. E 1 = 0 (vi behöver inget utbyte mot matris med ett element). Det genomsnittliga antalet utbyten för att sortera N-element-array är summan av det genomsnittliga antalet utbyten för att sortera N-1-elementarray med det genomsnittliga utbytet för att infoga det sista elementet i N-1-elementarray.
Förenkla summeringen (aritmetiska serier)
Utökar termen
Förenkla summeringen igen (aritmetiska serier)
Genomsnittlig jämförelse
Låt Cn vara det totala genomsnittliga antalet jämförelse med sorts matris med N element. C 1 = 0 (vi behöver ingen jämförelse på en elementarray). Det genomsnittliga antalet jämförelser för att sortera N-elementarray är summan av det genomsnittliga antalet jämförelser för att sortera N-1-elementarray med den genomsnittliga jämförelsen för att infoga det sista elementet i N-1-elementarrayen. Om det sista elementet är det största elementet behöver vi bara en jämförelse, om det sista elementet är det andra minsta elementet behöver vi N-1-jämförelse. Men om det sista elementet är det minsta elementet behöver vi inte N-jämförelse. Vi behöver fortfarande bara N-1 jämförelse. Det är därför vi tar bort 1 / N under ekvationen.
Förenkla summeringen (aritmetiska serier)
Utöka termen
Förenkla summeringen igen (aritmetiska serier och harmoniskt nummer)
Grundläggande om algoritmer
Insertion sort är en mycket enkel, stabil, på plats placeringsalgoritm. Det fungerar bra på små sekvenser men det är mycket mindre effektivt på stora listor. Vid varje steg beaktar algoritmerna det i-te elementet i den givna sekvensen och flyttar det till vänster tills det är i rätt position.
Grafisk illustration
pseudo
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
Exempel
Tänk på följande lista med heltal:
[5, 2, 4, 6, 1, 3]
Algoritmen kommer att utföra följande steg:
-
[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 # Implementering
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;
}
}
Hjälprum: O(1)
Tidskomplexitet: O(n)
Haskell-implementering
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
