Când sarcina dumneavoastră de sortare implică o gamă largă de mici "numarate," cum ar fi grade, vârste, sau coduri categorice de comparație clasice algoritmi bazate pe comparație, cum ar fi QuickSort sau MergeSort pot simți ca overkill. Aceste algoritmi rula în O [n log n) timp, dar în cazul în care gama de valori posibile este limitată, puteți sorta în liniară O(n + k) timp cu Counting Sortare. Acest algoritm de sortare non-comparison pârghie faptul că puteți conta evenimente, mai degrabă decât să comparați elemente, oferind un fel stabil, care este atât simplu și rapid pentru intrările potrivite.

Cum se numără lucrări de sortare

Numărarea Sortare exploatează cunoștințele că valorile de intrare sunt numere întregi extrase dintr-o gamă mică . În loc de comparații perechi, ea construiește o histogramă de frecvență a valorilor și apoi folosește histograma pentru a plasa fiecare element în poziția corectă sortate.

Abordarea de bază: Reconstrucţia directă

Cea mai simplă versiune a Counting Sortare funcționează în două permise:

  1. Număr de frecvențe
  2. Suprascrieți intrarea

Aceasta produce o ieșire sortate, dar nu [ păstrează ordinea relativă a duplicatelor (nu este stabilă). Stabilitatea contează atunci când sortați pe o cheie în timp ce țineți ordinea originală a înregistrărilor cu chei egale. Varianta stabilă, descrisă în continuare, este cea mai frecvent utilizată în practică.

Varianta stabilă: Conte cumulativ

Pentru a face Numărarea Sortare stabilă, adăugăm o a treia trecere:

  1. Numără frecvenţele ca înainte.
  2. Transformă matricea de frecvenţă într-un array cumulativ de numărare. După acest pas, deţine numărul de elemente ≤ i.
  3. Iterează matricea de intrare în sens invers (de la ultimul element la primul). Pentru fiecare element, utilizați numărul său cumulativ pentru a găsi poziția sa în matricea de ieșire, plasați-l, și decrement numărul.

Pentru că traversăm în sens invers, ordinea relativă a elementelor egale este păstrată. Array-ul de ieșire este separat de intrare, astfel încât această versiune utilizează O(n) spațiu suplimentar pentru ieșire, în timp ce versiunea de bază poate sorta în-loc prin suprascrierea de intrare.

Implementarea Numărare Sortare în C#

Mai jos sunt două implementări C#: versiunea de bază în loc (pentru scenarii în care stabilitatea este inutilă) și versiunea stabilă care utilizează un array auxiliar. Ambele necesită cunoașterea valorii maxime în avans.

Sortare de numărare de bază (non-stabil)

Această variantă sortează matricea de intrare direct fără un tampon de ieșire suplimentar. Este memorie-eficient, dar nu stabil.

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;
 }
 }
}

Sortare de numărare stabilă

Versiunea stabilă necesită o gamă de ieșire de aceeași dimensiune ca și intrarea. De asemenea, utilizează numere cumulative pentru a poziționa corect elementele.

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;
}

În ambele implementări, este cel mai mare număr întreg care apare în matrice. Dacă adevăratul maxim este necunoscut, îl puteți calcula cu o scanare pregătitoare (O(n)). Versiunea stabilă returnează un nou array sortat, lăsând originalul neschimbat.

Analiza complexității

n] să fie numărul de elemente și k = max

  • Timp:[ Numărare Sortare ruleaza in O(n + k) timp. Faza de numărare este O(n), prefixul cumulativ este O(k), iar reconstructia este O(n). Când k este O(n), algoritmul este liniar.
  • Space: Versiunea de bază folosește spațiu suplimentar pentru matricea de numărare.Versiunea stabilă folosește O(n + k) pentru că alocă și matricea de ieșire. Aceasta face ca numărul de ordine să fie nepotrivit atunci când intervalul este mare în raport cu numărul de elemente.
  • Comparison cu alte tipuri: Comparații pe bază de sorturi precum QuickSort și MergeSort necesită cel puțin O(n log n) comparații. Pentru k mici (de exemplu, k < 10000 și n > 100000), numărarea Sortare poate fi ordine de magnitudine mai rapidă.

Variații și extinderi

Manipularea Integerilor negativi

Numărarea Sortare funcționează nativ cu numere întregi non-negative. Pentru a manipula valorile negative, se schimbă întregul interval astfel încât minimul devine zero. De exemplu, dacă numerele variază de la -1000 la 1000, se compensează fiecare element de +1000. Array-ul de numărare are apoi dimensiunea .

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;
}

Mapping non-integer Keys

Numărarea Sortare necesită taste întregi. Dacă datele sunt formate din caractere (bytes), sau numere care pot fi exprimate la numere întregi, puteți aplica încă. Pentru obiecte mai mari, puteți extrage o cheie întreg și sorta obiectele în consecință . Acesta este exact modul în care Radix Sortează folosește adesea Numărarea Sortare ca subrutină interioară.

Radix Sortare Combo

Radix Sortare process digits (sau bits) individual, și Numărare Sortare este alegerea naturală pentru fiecare trecere atunci când baza (de exemplu, 10 sau 256) este mic. Aceasta permite sortarea liniară-timp a numerelor arbitrare, nu doar cele mici.

Considerații practice în C#

Amprenta de memorie și K mare

Cea mai mare capcană este alocarea unui număr de matrice mai mare decât memoria disponibilă. De exemplu, sortarea 1.000 de elemente cu o gamă de 1.000.000 de deșeuri spațiu. Verificați întotdeauna că k nu este ordine de magnitudine mai mare decât n][FLT:]] Altă metodă utilizează în mod alternativ un tip de comparație sau o abordare hibridă.

Paralelism şi Span<T>

Pentru array-uri extrem de mari, puteți paraleliza faza de numărare prin partiționarea intrare peste fire. Fiecare fir contează segmentul său într-un array privat, iar apoi rezultatele parțiale sunt agregate. Folosind și pentru matricea de numărare poate reduce alocările grămadă atunci când gama este mică.

Cauze de margine

  • Array gol ]
  • Element unic
  • Toate valorile identice
  • Date mari, dar puţine

Recomandări privind performanța

Utilizați Sort de numărare atunci când știți că numărul total de intrare se încadrează într-o gamă mică (de exemplu, gradele 0

Când să utilizați Sortare Numărare (și când nu)

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.

Analize de referință și performanță

Într-un criteriu tipic cu n = 1.000.000 și k = 1000, Sortul de numărare se completează în aproximativ 20 ian. din timpul scurs de (care folosește introsort). Decalajul se lărgește pe măsură ce k scade. Mai jos este o comparație aproximativă (timpurile de execuție pe un proces modern cu .NET 8):

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

Când gama crește la 10.000, Counting Sorting câștigă încă, dar marja se îngustează. Pentru k = 100.000, memoria deasupra (

Concluzie

Numărarea Sortare este un algoritm înșelător de simplu care oferă performanță liniară atunci când datele se potrivesc constrângerilor sale. Pentru dezvoltatorii C# care se ocupă cu array-uri mari de numere mici, este un instrument valoros care poate reduce dramatic timpul de sortare. Păstrați un ochi pe gama de date: dacă este mic și cunoscut, Sortare de numărare va depăși orice alternativă bazată pe comparație. Pentru sortarea mai generală, utilizați built-in , dar fiți întotdeauna gata să scadă în numărare Sortare atunci când numerele se aliniază în sus literalmente și figurativ.

Pentru lectură ulterioară, consultați Wikipedia articol despre Numărare Sortare, Microsoft docs on Array.Sort, și un ghid practic de la Geeks for Geeks.