min_index =j
slut om
upphöra med
// byt det hittade minsta elementet med det första elementet
Swap List [i] och lista [min_index]
upphöra med
slutförfarande
`` `
* Effektivitet:
* bästa fall: O (n
2
)
* Genomsnittligt fall: O (n
2
)
* värsta fall: O (n
2
)
* Rymdkomplexitet: O (1) (på plats sort)
* Implementering: Relativt enkelt.
* Användningsfall: Utför något bättre än bubbelsortering i vissa fall, men är fortfarande inte lämplig för stora datasätt. Antalet swappar är begränsat till O (n), vilket kan vara användbart om minnesskrivningar är dyra.
3. Insättningssortering
* koncept: Bygger den sorterade listan ett element i taget. Det itererar genom inmatningsdata, tar bort ett element åt gången, hittar rätt position för den i den sorterade listan och sätter in dem där.
* pseudocode:
`` `
Procedur InsertionSort (Lista:Array of Objekt)
n =längd (lista)
för i =1 till n-1 do
NYCKEL =lista [i]
J =i - 1
// Flytta element i listan [0..i-1], som är större än nyckeln,
// till en position före sin nuvarande position
Medan j> =0 och lista [j]> nyckel gör
Lista [J+1] =lista [J]
j =j - 1
slut
lista [J+1] =nyckel
upphöra med
slutförfarande
`` `
* Effektivitet:
* bästa fall: O (n) (när listan redan är sorterad)
* Genomsnittligt fall: O (n
2
)
* värsta fall: O (n
2
)
* Rymdkomplexitet: O (1) (på plats sort)
* Implementering: Enkelt och effektivt för små datasätt eller nästan sorterade data.
* Användningsfall: Bra för små listor eller när du förväntar dig att inmatningsdata mest sorteras. Det är också en * online * algoritm som betyder att den kan sortera en lista som den tar emot den.
4. Slå samman sortering
* koncept: En uppdelnings- och erövringsalgoritm. Den delar upp listan i mindre sublistor, sorterar rekursivt sublistorna och slås sedan samman dem igen.
* pseudocode:
`` `
procedur sammanslagning (lista:matris)
n =längd (lista)
Om n <=1 då
returlista // redan sorterat
slut om
// Dela upp listan i två halvor
Mid =n / 2
Vänsterlista =lista [0 till mitten av 1]
RightList =List [Mid to N-1]
// Rekursivt sortera varje hälft
vänsterlista =sammanslagning (vänsterlista)
högerlista =sammanslagning (högerlista)
// slå samman de sorterade halvorna
Return Merge (vänsterlista, högerlista)
slutförfarande
Procedurfusion (vänsterlista:Array of Objects, RightList:Array of Objekt)
ResultList =new Array
Medan vänsterlistan inte är tom och högerlista är inte tomt gör
Om vänsterlista [0] <=högerlista [0] då
bifoga vänsterlista [0] till resultatlistan
Ta bort vänsterlistan [0] från vänsterlistan
annan
bifoga högerlista [0] till resultatslistan
Ta bort högerlista [0] från högerlista
slut om
slut
// lägg till alla återstående element från vänsterlista eller högerlista
Lägg till alla återstående delar av vänsterlistan till resultatslistan
Lägg till alla återstående delar av högerlista till resultatslistan
returlista
slutförfarande
`` `
* Effektivitet:
* bästa fall: O (n log n)
* Genomsnittligt fall: O (n log n)
* värsta fall: O (n log n)
* Rymdkomplexitet: O (n) (kräver extra utrymme för sammanslagning)
* Implementering: Mer komplex än de tidigare algoritmerna, men ger bra prestanda för stora datasätt.
* Användningsfall: Lämplig för att sortera stora listor där konsekvent prestanda är viktig.
5. Snabbsortering
* koncept: Också en uppdelnings- och erövringsalgoritm. Det väljer ett element som en pivot och partitioner den givna matrisen runt den plockade pivoten.
* pseudocode:
`` `
Procedur QuickSort (Lista:Array of Objects, Low:Int, High:Int)
Om låg
// Partitioning Index, ARR [P] är nu på rätt plats
P =partition (lista, låg, hög)
// Separat sortera element före partition och efter partition
Quicksort (lista, låg, p-1)
Quicksort (Lista, P+1, High)
slut om
slutförfarande
procedurpartition (lista:matris, låg:int, hög:int)
pivot =lista [hög] // välj det sista elementet som pivot
I =låg - 1 // Index för mindre element
för J =låg till high-1 do
// Om det nuvarande elementet är mindre än eller lika med pivot
Om listan [j] <=pivot då
i =i + 1 // inkrementindex för mindre element
Swap List [i] och lista [J]
slut om
upphöra med
Swap List [i + 1] och List [High]
Return i + 1
slutförfarande
`` `
* Effektivitet:
* bästa fall: O (n log n) (när pivoten alltid är medianen)
* Genomsnittligt fall: O (n log n)
* värsta fall: O (n
2
) (När pivoten alltid är det minsta eller största elementet)
* Rymdkomplexitet: O (log n) (på grund av rekursiva samtal kan vara o (n) i värsta fall)
* Implementering: Generellt snabbt i praktiken, men dess värsta fall kan vara ett problem. Valet av pivot påverkar avsevärt dess prestanda.
* Användningsfall: Ofta den snabbaste sorteringsalgoritmen i praktiken för stora datasätt. Men dess värsta fall måste beaktas. Många implementeringar använder randomisering eller andra tekniker för att undvika värsta fall.
6. Heap Sort
* koncept: Bygger en maxhög (eller min hög) från ingångsdata och extraherar sedan upprepade gånger rotelementet (det största eller minsta elementet) och placerar det i slutet av den sorterade arrayen.
* pseudocode:
`` `
Procedur Heapsort (lista:Array of Objekt)
n =längd (lista)
// Bygg maxhögen
för i =n/2 - 1 ner till 0 do
Heapify (List, N, I)
upphöra med
// en efter ett extrakt ett element från högen
för i =n-1 ner till 0 do
Swap List [0] och List [i] // flytta aktuell rot till slut
// ring max heapify på den reducerade högen
Heapify (List, I, 0)
upphöra med
slutförfarande
Procedur Heapify (Lista:Array of Poster, N:Int, I:Int)
största =i // initialisera största som rot
vänster =2*i + 1
höger =2*i + 2
// Om vänsterbarn är större än rot
Om vänster lista [största] då
största =vänster
slut om
// Om rätt barn är större än största hittills
Om höger lista [största] då
Största =rätt
slut om
// Om största är inte rot
Om största! =I då
Swap List [i] och lista [största]
// Rekursivt strävar efter det drabbade underträdet
Heapify (lista, n, största)
slut om
slutförfarande
`` `
* Effektivitet:
* bästa fall: O (n log n)
* Genomsnittligt fall: O (n log n)
* värsta fall: O (n log n)
* Rymdkomplexitet: O (1) (på plats sort)
* Implementering: Mer komplexa än enklare algoritmer, men garanterar o (n log n) prestanda.
* Användningsfall: Ett bra val när du behöver garanterad o (n log n) prestanda och på plats sortering är önskvärt. Används i implementeringar av prioritetskö.
Sammanfattningstabell över effektivitet
| Algoritm | Bästa fallet | Genomsnittligt fall | Värsta fall | Rymdkomplexitet |
| ------------------- | ----------- | -------------- | ------------ | ----------------------- |
| Bubble Sort | O (n) | O (n
2
) | O (n
2
) | O (1) |
| Urval sortering | O (n
2
) | O (n
2
) | O (n
2
) | O (1) |
| Insättningssortering | O (n) | O (n
2
) | O (n
2
) | O (1) |
| Slå samman sortering | O (n log n) | O (n log n) | O (n log n) | O (n) |
| Snabbsortering | O (n log n) | O (n log n) | O (n
2
) | O (log n) |
| Heap Sort | O (n log n) | O (n log n) | O (n log n) | O (1) |
Nyckelskillnader i effektivitet och implementering:
* Kvadratiska kontra logaritmiska: Algoritmer med O (n
2
) Effektivitet (bubbla, urval, insättning) är endast lämpliga för små datasätt. Algoritmer med O (n log n) Effektivitet (sammanslagning, snabb, hög) är mycket effektivare för större datasätt.
* divide and conquer: Slå samman sortering och snabb sortering Använd klyftan och erövringsstrategin, som möjliggör effektivare sortering av stora datasätt.
* på plats sortering: Bubble sortering, urvalssortering, infogningssortering och högsortering är på plats sorteringsalgoritmer, vilket innebär att de inte kräver betydande extra minne. Slå samman sort kräver o (n) extra utrymme för sammanslagning. Snabbsorter kräver i genomsnitt o (log n) men o (n) utrymme i värsta fall på grund av de rekursiva samtalen.
* stabilitet: En sorteringsalgoritm är * stabil * om element med lika värden upprätthåller sin relativa ordning efter sortering. Släppsortering och införingssortering är stabila, medan högsortering och snabb sortering (i deras grundläggande form) inte är det. Stabilitet kan vara viktig i vissa applikationer.
* pivot val (snabb sort): Prestandan för snabb sort är starkt beroende av valet av pivotelementet. Dåliga pivotval kan leda till värsta fall O (n
2
) prestanda.
* Komplexiteten i implementeringen: Bubble sortering och införingssortering är det enklaste att implementera. Slå samman sortering, snabb sortering och högsorter är mer komplexa.
* Adaptivitet: Insättningssortering är anpassningsbar, vilket innebär att prestandan förbättras om ingångsdata redan är delvis sorterade.
Att välja rätt algoritm:
Den bästa sorteringsalgoritmen som ska användas beror på den specifika applikationen och egenskaperna hos data. Tänk på dessa faktorer:
* storleken på datasättet: För mycket små datasätt kan enkelheten i bubbelsortering eller insättningssortering vara tillräcklig. För större datasätt är sammanslagningssortering, snabb sortering eller högsorter i allmänhet bättre val.
* sorteringsnivå: Om uppgifterna redan är sorterade, kan insättningssortering vara det snabbaste alternativet.
* Minnesbegränsningar: Om minnet är begränsat, föredras på plats sortering av algoritmer som bubbelsorter, urvalssortering, infogningssortering och högsortering.
* Stabilitetskrav: Om stabilitet krävs, välj en stabil sorteringsalgoritm som sammanslagningssortering eller insertionssortering.
* Värsta fall: Om du behöver garanterad prestanda, undvik snabb sortering (såvida det inte implementeras med pivot-randomisering eller andra strategier för att mildra beteende i värsta fall).
* enkel implementering och underhåll: Tänk på avvägningen mellan prestanda och komplexitet i implementeringen.
Jag hoppas att denna detaljerade förklaring hjälper! Låt mig veta om du har ytterligare frågor.
