Met letterlijk tientallen sorteeralgoritmes beschikbaar , het bepalen welke het beste werkt met uw systeem zal afhangen van vergelijkingen van verschillende factoren , zoals de grootte van de lijst , de snelheid of de complexiteit van het algoritme , en of u zal een sleutel te gebruiken om te sorteren . Complexiteit De complexiteit van een sorteer-algoritme wordt gemeten door O ( n ) , of de " orde van n ' waarbij n de grootte van de lijst . Het meet hoeveel gaat het duurt om de lijst te sorteren en berekent de beste , slechtste en gemiddelde tijd om dit te doen . Voorkomende complexiteiten omvatten n als beste geval voor soorten zoals insertion sort en shell sorteren , n log n , ( met behulp van een base - 2 logaritme , niet een basis - 10 ) , die de complexiteit voor de merge sort en HeapSort , en n ² , dat is langzamer dan de eerste keer en is de snelheid voor de selectie sorteren list Conditie Soms zult u weten hoe het ongesorteerde items in een lijst worden georganiseerd . : bijvoorbeeld , of ze zijn bijna gesorteerd , in omgekeerde volgorde , of een lijst met enkele unieke items . Deze kennis helpt u een efficiënt algoritme om het te sorteren te selecteren . Bijvoorbeeld met behulp van insertion sort om een lijst te sorteren in omgekeerde volgorde heeft een looptijd van n ² , terwijl heap sort kan doen sneller , in n log n tijd . Op een lijst die bijna is gesorteerd , insertion sort is sneller dan heap sort . Wanneer de lijst bevat een compleet willekeurig set van gegevens , selecteert u een algoritme met een gemiddelde case complexiteit van n log n looptijd , zoals heap sort , quicksort of samenvoegen soort . List Grootte Sommige algoritmen zijn moeilijker te gebruiken dan anderen , dus het aantal elementen in een lijst en hoe vaak je nodig hebt om te sorteren kan helpen bij het bepalen van het algoritme u kiest . Soorten zoals insertion sort zijn snel en werken goed bij het sorteren kleinere lijsten , en zijn eenvoudig te implementeren , maar ze zijn traag met grotere lijsten . Soorten die een verdeel - en -heers -algoritme zoals quicksort en merge sort gebruiken zijn moeilijker te implementeren , maar ze sorteren grotere lijsten sneller in de gemiddelde gevallen . Stabiliteit algoritme stabiliteit beschrijft of de soort handhaaft de volgorde van de items op basis van een sorteer- toets. Bijvoorbeeld met behulp van het eerste teken als een sleutel voor een lijst die " John , " " Steve " en " Jim heeft " in die volgorde , een stabiele algoritme sorteert de lijst " John , " " Jim " en " Steve , " terwijl een instabiele algoritme kan wel of niet sorteren " Jim " voor " John . " Sorteren samenvoegen , insertion sort en bubble sort zijn allemaal stabiel algoritmes terwijl shell sort , selectie sorteren en heap sort niet .
|