När din sorteringsuppgift involverar stora mängder små heltal - som grader, åldrar eller kategoriska koder - kan de klassiska jämförelsebaserade algoritmerna som QuickSort eller MergeSort känna sig som overkill. Dessa algoritmer körs i O(n log n) tid, men om intervallet av möjliga värden är begränsad, kan du sortera i linjär O(n + k) tid med Räkna Sort

Hur greve Sort fungerar

Räkna Sort utnyttjar kunskapen om att ingångsvärdena är heltal som dras från ett litet intervall ]]. I stället för parvisa jämförelser bygger den ett frekvenshitogram av värdena och använder sedan att histogram för att placera varje element i sin korrekta sorterade position.

Grundläggande strategi: direkt rekonstruktion

Den enklaste versionen av Counting Sort fungerar i två pass:

  1. ] Räkna frekvenser[ - Sätt dig genom ingångsarrayen och steg en räknare för varje värde du ser.
  2. Skriv ingången - Gå genom disken array från minst till största och, för varje värde, skriva tillbaka den till ingångsarrayen så många gånger som dess räkna.

Detta ger en sorterad utgång men gör ] inte []] bevara den relativa ordningen av dubbletter (det är inte stabilt). Stabilitet är viktigt när du sorterar på en nyckel medan du håller den ursprungliga ordningen av poster med lika nycklar. Den stabila varianten, som beskrivs nästa, är den som oftast används i praktiken.

Stabil Variant: Kumulativa grejer

För att göra greve Sort stabil, lägger vi till ett tredje pass:

  1. Räkna frekvenser som tidigare.
  2. Omvandla frekvensen till en kumulativ räkning. Efter detta steg håller antalet element ≤ ]i ].
  3. Sätt ingångsarrayen i omvänd (från sista elementet till början). För varje element, använd dess kumulativa räkning för att hitta sin position i utgångsarrayen, placera den och dekretera räkningen.

Eftersom vi korsar i omvänd, den relativa ordningen av lika element bevaras. Utgångsarrayen är separat från ingången, så denna version använder O(n) extra utrymme för utgången, medan den grundläggande versionen kan sortera på plats genom att skriva ingången.

Implementering av greve Sort i C#

Nedan följer två C#-implementeringar: den grundläggande versionen (för scenarier där stabiliteten är onödig) och den stabila versionen som använder en hjälparray. Båda kräver att du vet det maximala värdet i förväg.

Grundläggande (icke-stabil) greve Sort

Denna variant sorterar ingångsarrayen direkt utan en extra utgångsbuffert. Det är minneseffektivt men inte stabilt.

public static void CountingSortBasic(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];

 // Count each element's frequency
 for (int i = 0; i < array.Length; i++)
 {
 counts[array[i]]++;
 }

 // Overwrite the original array in sorted order
 int index = 0;
 for (int value = 0; value <= maxValue; value++)
 {
 while (counts[value]-- > 0)
 {
 array[index++] = value;
 }
 }
}

Stabil greve Sort

Den stabila versionen kräver en utgångsarray av samma storlek som ingången. Den använder också kumulativa räkningar till positionselement korrekt.

public static int[] CountingSortStable(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];
 int[] output = new int[array.Length];

 // Step 1: Count occurrences
 foreach (int num in array)
 {
 counts[num]++;
 }

 // Step 2: Transform counts to cumulative counts
 for (int i = 1; i <= maxValue; i++)
 {
 counts[i] += counts[i - 1];
 }

 // Step 3: Build the output array (iterate input in reverse for stability)
 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value] - 1] = value;
 counts[value]--;
 }

 return output;
}

I båda genomförandena är det största heltal som visas i matrisen. Om det sanna maximumet är okänt kan du beräkna det med en förberedande skanning (O(n)). Den stabila versionen returnerar en ny sorterad matris, vilket lämnar den ursprungliga oförändrade.

Komplexitetsanalys

]][]]]]] vara antalet element och ]]][]] = max - min + 1 (omfånget av möjliga värden).

  • ]]Tid:[ Räkna Sort går i ]O(n + k)]]]]] tid. Räknandefasen är O(n), kumulativ prefixet är O(k), och rekonstruktionen är O(n). När k är O(n), algoritmen är linjär.
  • Space:[] Den grundläggande versionen använder O(k) extra utrymme för räkningen. Den stabila versionen använder O(n + k) eftersom den också fördelar utgångsarrayen. Detta gör att Counting Sort olämpligt när intervallet är stort i förhållande till antalet objekt.
  • ] Jämförelse med andra sorter:[ Jämförelsebaserade sorter som QuickSort och MergeSort kräver åtminstone O(n log n) jämförelser. För små k (t.ex. k < 10 000 och n > 100.000), Räkna Sort kan vara storleksordningar snabbare.

Variationer och förlängningar

Hantera negativa integers

Räkna Sort fungerar inhemskt med icke-negativa heltal. För att hantera negativa värden, flytta hela sortimentet så att minimum blir noll. Till exempel, om siffrorna sträcker sig från -1000 till 1000, kompensera varje element med +1000. Räknat array har sedan storlek .

public static int[] CountingSortWithNegative(int[] array)
{
 if (array.Length == 0) return array;

 int min = array.Min();
 int max = array.Max();
 int range = max - min + 1;

 int[] counts = new int[range];
 int[] output = new int[array.Length];

 foreach (int num in array)
 counts[num - min]++;

 for (int i = 1; i < range; i++)
 counts[i] += counts[i - 1];

 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value - min] - 1] = value;
 counts[value - min]--;
 }

 return output;
}

Kartläggning av icke-integernycklar

Räkna Sort kräver heltalsnycklar. Om dina data består av tecken (byte), eller uppräkningar som kan kastas till heltal, kan du fortfarande tillämpa det. För större objekt kan du extrahera en heltalsnyckel och sortera objekten i enlighet därmed - det är exakt hur Radix Sort ofta använder Räkna Sort som sin inre subroutin.

Radix Sort Combo

Radix Sort processer siffror (eller bitar) individuellt, och greve Sort är det naturliga valet för varje pass när basen (t.ex. 10 eller 256) är liten. Detta gör det möjligt linjär tid sortering av godtyckliga heltal, inte bara små.

Praktiska överväganden i C#

Minnesfotavtryck och stor k

Den största fallgropen fördelar en räkning större än det tillgängliga minnet. Till exempel sorterar 1000 element med en rad av 1.000.000 avfall utrymme. Alltid verifiera att ]] k inte är storleksordningar större än ]] n - annars använder en jämförelse sort eller en hybrid tillvägagångssätt.

Parallelism och Span<T>

För extremt stora arrays kan du parallellisera räknande fas genom att partitionera ingången över trådar. Varje tråd räknar sitt segment i en privat array, och sedan de partiella resultaten aggregeras. Använda och för räkningen kan minska heapallokeringar när intervallet är litet.

Edge Cases

  • ] ]]] - returnera omedelbart.
  • ] Ensamstående element - sortering är trivial.
  • Alla identiska värden - räknartet har en icke-noll ingång; rekonstruktionen körs i O(n).
  • ]Large range but sparse data - Räkna Sort blir ineffektivt eftersom de flesta räkningsposter är noll. Tänk på en hash-baserad räkna tillvägagångssätt eller Bucket Sort.

Prestandarekommendationer

Använd greve Sort när du vet att ingångsintegren faller i ett litet intervall (t.ex. betyg 0-100, åldrar 0-120 eller felkoder 0-255). För större intervall, överväga Radix Sort eller en hybrid som faller tillbaka till QuickSort för högklassiga partitioner.

När du ska använda greve Sort (och när du inte ska)

SituationRecommendation
Small integer range (k ~ n)Excellent choice – linear time, simple code.
Large integer range (k >> n)Avoid – memory waste and O(k) overhead.
Need stabilityUse the stable variant (cumulative counts).
Strings or objectsConsider Radix Sort or a comparison sort.
Extremely large datasetsCounting Sort can be parallelized; but watch memory.

Benchmarking och prestanda

I ett typiskt referensvärde med n = 1 000 000 och k = 1 000, Counting Sort slutförs i cirka 20-30% av den tid som tagits av (som använder introsort). Gapet breddar som k minskar. Nedan är en ungefärlig jämförelse (föreförandetider på en modern CPU med .NET 8):

n = 1,000,000 | k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic : 12 ms
CountingSortStable : 18 ms

När intervallet växer till 10 000, Counting Sort fortfarande vinner, men marginalen smalnar. För k = 100.000, minnet överhuvudet (≈ 400 KB för räkna array) börjar skada CPU cache, och prestanda kan försämras.

Slutsats

Räkna Sort är en bedrägligt enkel algoritm som levererar linjär prestanda när data passar sina begränsningar. För C# utvecklare som arbetar med stora mängder små heltal, är det ett värdefullt verktyg som dramatiskt kan minska sorteringstiden. Håll ett öga på intervallet av dina data: om det är litet och känt, kommer greve Sort att överträffa alla jämförelsebaserade alternativ. För mer allmänt ändamål sortering, använd inbyggd , men alltid vara redo att släppa i gre Sort när siffrorna upp -

För vidare läsning, rådfråga ]Wikipedia artikeln om greve Sort , ]]]Microsoft docs on Array.Sort ]] och en praktisk guide från ]]GeeksforGeeks]].