Med bogstaveligt snesevis af sortering algoritmer til rådighed , afgøre, hvilke der fungerer bedst med dit system vil afhænge af sammenligninger af flere faktorer, såsom størrelsen af listen , hastigheden eller kompleksitet af algoritmen , og om du vil bruge en nøgle til at sortere . Kompleksitet
kompleksiteten i en sorteringsalgoritme måles ved O ( n ) , eller " orden n ", hvor n er størrelsen på listen. Den måler , hvor mange passerer , det tager at sortere listen og beregner sit bedste, værste og gennemsnitlige tid til at gøre det . Almindelige kompleksitet indbefatter n som en bedste fald med sorterer såsom indsættelse sortere og shell sortere , n log n , ( anvendelse af en base - 2 logaritmen , ikke en base - 10 ) , som er den kompleksitet for sammenfletningen sortere og heapsort , og n ² , hvilket er langsommere end første gang, og er hastigheden for udvælgelse sortere
List betingelse
Nogle gange vil du vide, hvordan de usorterede elementer på en liste er organiseret . : for eksempel, om der er næsten sorteres i omvendt rækkefølge , eller en liste med få unikke elementer . En sådan viden hjælper dig vælge en effektiv algoritme til at sortere det . For eksempel har bruger indsættelse slags til at sortere en liste i omvendt rækkefølge en spilletid n ², mens heap art kan gøre det hurtigere , i n log n tid. På en liste, der er næsten sorteret, er indsættelse sortere hurtigere end bunke slags. Når listen indeholder et helt randomiseret datasæt , skal du vælge en algoritme med en gennemsnitlig tilfælde kompleksiteten af n log n køretid , såsom bunke sortere, quicksort eller flette slags.
List Size
Nogle algoritmer er sværere at bruge end andre, så antallet af elementer på en liste , og hvor ofte du har brug for at sortere kan hjælpe med at bestemme den algoritme , du vil vælge . Sorterer som indsættelse sortere er hurtige og fungere godt, når sortering mindre lister , og er nemme at gennemføre, men de er langsomme med større lister. Sorterer , der bruger en del-og -hersk algoritme som quicksort og merge slags er sværere at gennemføre, men de sortere større lister hurtigere i de gennemsnitlige tilfælde.
Stabilitet
Algoritme stabilitet beskriver , hvorvidt den slags fastholder rækkefølgen af elementer baseret på en sortering tast. For eksempel, " , Steve " ved hjælp af første tegn som en nøgle for en liste , der har " Johannes ", " Steve " og " Jim" i nævnte rækkefølge , en stabil algoritme sorterer listen til " John ", " Jim" , og mens en ustabil algoritme kan eller ikke kan sortere " Jim " før " John ". Flet sortere, indsættelse sortere og boble sortere er alle stabile algoritmer , mens shell sortere, udvælgelse sortere og heap sortere ikke er.