algorithm
Sortering
Sök…
parametrar
| Parameter | Beskrivning |
|---|---|
| Stabilitet | En sorteringsalgoritm är stabil om den bevarar den relativa ordningen för lika element efter sortering. |
| På plats | En sorteringsalgoritm är på plats om den sorterar med hjälp av endast O(1) hjälpminne (inte räknar den matris som behöver sorteras). |
| Bästa fall komplexitet | En sorteringsalgoritm har en bästa falltidskomplexitet på O(T(n)) om dess driftstid är minst T(n) för alla möjliga ingångar. |
| Genomsnittlig fallkomplexitet | En sorteringsalgoritm har en genomsnittlig falltidskomplexitet på O(T(n)) om dess körtid, i genomsnitt över alla möjliga ingångar , är T(n) . |
| Värsta fall komplexitet | En sorteringsalgoritm har ett värsta fallskomplexitet på O(T(n)) om dess körtid är högst T(n) . |
Stabilitet i sortering
Stabilitet vid sortering innebär om en sorteringsalgoritm upprätthåller den relativa ordningen för lika tangenterna för den ursprungliga ingången i resultatutgången.
Så en sortsalgoritm sägs vara stabil om två objekt med lika tangenter visas i samma ordning i sorterad utgång som de visas i den osorterade matchen.
Överväg en lista med par:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Nu kommer vi att sortera listan med det första elementet i varje par.
En stabil sortering av listan ger följande lista:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Eftersom (9, 3) visas efter (9, 7) i originallistan.
En instabil sortering ger nedanstående lista:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
Instabil sortering kan generera samma utgång som den stabila sorteringen, men inte alltid.
Kända stabila sorter:
Välkända instabila sorter:
Modified text is an extract of the original Stack Overflow Documentation
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow
