Όταν η εργασία διαλογής περιλαμβάνει μεγάλες σειρές μικρών ακέραιων ⁇ όπως βαθμούς, ηλικίες ή κατηγορητικούς κώδικες ⁇ οι κλασικοί αλγόριθμοι σύγκρισης όπως το QuickSort ή το MergeSort μπορούν να νιώσουν υπερβολή. Αυτοί οι αλγόριθμοι τρέχουν σε χρόνο O(n log n), αλλά αν το εύρος των πιθανών τιμών είναι περιορισμένο, μπορείτε να ταξινομήσετε σε γραμμικό χρόνο O(n + k) με Ταξινόμηση . Αυτός ο αλγόριθμος ταξινόμησης χωρίς σύγκρισης μοχλεύει το γεγονός ότι μπορείτε να μετρήσετε τα φαινόμενα αντί να συγκρίνετε στοιχεία, παρέχοντας ένα σταθερό είδος που είναι τόσο απλό όσο και λαμπερά γρήγορο για τις σωστές εισροές.

Πώς λειτουργεί η Μέτρηση

Μετρώντας Το Ταξινόμηση εκμεταλλεύεται τη γνώση ότι οι τιμές εισόδου είναι ακέραιοι που αντλούνται από ένα μικρό εύρος [[LFT:0]]]. Αντί για συγκρίσεις κατά ζεύγη, κατασκευάζει ένα ιστόγραμμα συχνότητας των τιμών και στη συνέχεια χρησιμοποιεί ότι το ιστόγραμμα για να τοποθετήσει κάθε στοιχείο στη σωστή ταξινομημένη θέση του.

Η βασική προσέγγιση: Άμεση αναδόμηση

Η απλούστερη έκδοση του Counting Sort λειτουργεί σε δύο περάσματα:

  1. Συχνότητες καταμέτρησης ⁇ Επαναλάβετε μέσω της διάταξης εισόδου και αυξήστε έναν μετρητή για κάθε τιμή που βλέπετε.
  2. Επιστρέψτε την είσοδο ⁇ Περπατήστε μέσα από την παράταξη μετρητή από τη μικρότερη στη μεγαλύτερη και, για κάθε τιμή, γράψτε την πίσω στη διάταξη εισόδου τόσες φορές όσο και ο αριθμός της.

Αυτό αποδίδει μια ταξινομημένη έξοδο, αλλά δεν [[LFT:0]] δεν διατηρεί [[[LFT:1]] τη σχετική σειρά των διπλών (δεν είναι σταθερή).Η σταθερότητα έχει σημασία όταν ταξινομείτε σε ένα κλειδί, ενώ κρατάτε την αρχική σειρά των αρχείων με ίσα πλήκτρα. Η σταθερή παραλλαγή, που περιγράφεται στη συνέχεια, είναι αυτή που χρησιμοποιείται πιο συχνά στην πράξη.

Η Σταθερή Παραλλαγή: Αθροιστικές Μετρήσεις

Για να κάνουμε την μέτρηση Ταξινόμηση σταθερή, προσθέτουμε ένα τρίτο πέρασμα:

  1. Μετρήστε τις συχνότητες όπως πριν.
  2. Μετά από αυτό το βήμα, κατέχει τον αριθμό των στοιχείων ≤ i.
  3. Επαναλάβετε τη διάταξη εισόδου στην αντίστροφη (από το τελευταίο στοιχείο στην πρώτη). Για κάθε στοιχείο, χρησιμοποιήστε το αθροιστικό του αριθμό για να βρείτε τη θέση του στη διάταξη εξόδου, τοποθετήστε το, και αποσβέστε την καταμέτρηση.

Επειδή διασχίζουμε αντίστροφα, διατηρείται η σχετική σειρά ίσων στοιχείων. Η διάταξη εξόδου είναι ξεχωριστή από την είσοδο, έτσι αυτή η έκδοση χρησιμοποιεί πρόσθετο χώρο O(n) για την έξοδο, ενώ η βασική έκδοση μπορεί να ταξινομήσει στην θέση της με την αντικατάσταση της εισόδου.

Εφαρμογή μέτρησης Ταξινόμηση στο C#

Παρακάτω βρίσκονται δύο υλοποιήσεις C#: η βασική in-place έκδοση (για σενάρια όπου η σταθερότητα είναι περιττή) και η σταθερή έκδοση που χρησιμοποιεί μια βοηθητική συστοιχία. Και οι δύο απαιτούν να γνωρίζουν τη μέγιστη τιμή εκ των προτέρων.

Βασικό (Μη σταθερό) Ταξινόμηση μέτρησης

Αυτή η παραλλαγή ταξινομεί τη διάταξη εισόδου άμεσα χωρίς επιπλέον ρυθμιστή εξόδου. Είναι μνήμη ⁇ αποτελεσματική αλλά όχι σταθερή.

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

Ταξινόμηση μέτρησης σταθερών

Η σταθερή έκδοση απαιτεί μια διάταξη εξόδου του ίδιου μεγέθους με την είσοδο. Χρησιμοποιεί επίσης σωρευτικά μετρήσεις για να τοποθετήσετε τα στοιχεία σωστά.

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

Και στις δύο υλοποιήσεις, είναι ο μεγαλύτερος ακέραιος που εμφανίζεται στη συστοιχία. Αν το πραγματικό μέγιστο είναι άγνωστο, μπορείτε να το υπολογίσετε με μια προκαταρκτική σάρωση (O(n)). Η σταθερή έκδοση επιστρέφει μια νέα ταξινομημένη συστοιχία, αφήνοντας την αρχική αναλλοίωτη.

Ανάλυση πολυπλοκότητας

Ας είναι n ο αριθμός στοιχείων και k = max ⁇ min + 1 (το εύρος των πιθανών τιμών).

  • Χρόνος: Μετρώντας Το Sort τρέχει σε O(n + k) χρόνο. Η φάση καταμέτρησης είναι O(n), το αθροιστικό πρόθεμα είναι O(k), και η ανακατασκευή είναι O(n). Όταν το k είναι O(n), ο αλγόριθμος είναι γραμμικός.
  • Διαστήματος: Η βασική έκδοση χρησιμοποιεί επιπλέον χώρο O(k) για τη συστοιχία καταμέτρησης. Η σταθερή έκδοση χρησιμοποιεί O(n + k) επειδή επίσης κατανέμει τη συστοιχία εξόδου. Αυτό καθιστά την μέτρηση Ταξινόμηση ακατάλληλη όταν η σειρά είναι μεγάλη σε σχέση με τον αριθμό των αντικειμένων.
  • Συγκριτική με άλλα είδη: Σύγκριση ⁇ με βάση είδη όπως QuickSort και MergeSort απαιτούν τουλάχιστον O(n log n) συγκρίσεις. Για μικρά k (π.χ., k & lt; 10.000 και n > 100.000), η μέτρηση Ταξινόμηση μπορεί να είναι τάξεις μεγέθους γρηγορότερα.

Παραλλαγές και επεκτάσεις

Χειρισμός Αρνητικών Ακέραιων

Για να χειριστεί τις αρνητικές τιμές, μετατοπίστε όλο το εύρος έτσι ώστε το ελάχιστο να γίνει μηδέν. Για παράδειγμα, αν οι αριθμοί κυμαίνονται από -1000 έως 1000, αντισταθμίζουν κάθε στοιχείο με +1000. Η σειρά καταμέτρησης τότε έχει μέγεθος .

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

Χαρτογράφηση μη ακέραιων κλειδιών

Αν τα δεδομένα σας αποτελούνται από χαρακτήρες (bytes), ή απαρίθμηση που μπορεί να χυθεί σε ακέραιους, μπορείτε ακόμα να το εφαρμόσετε. Για μεγαλύτερα αντικείμενα, μπορείτε να εξαγάγετε ένα ακέραιο κλειδί και να ταξινομήσετε τα αντικείμενα ανάλογα ⁇ αυτό είναι ακριβώς το πώς Radix Ταξινόμηση χρησιμοποιεί την μέτρηση Ταξινόμηση ως εσωτερική υπορουτίνα του.

Εύρος μεγέθους Combo

Radix Ταξινόμηση επεξεργασιών ψηφία (ή bits) μεμονωμένα, και η μέτρηση Ταξινόμηση είναι η φυσική επιλογή για κάθε πέρασμα όταν η βάση (π.χ., 10 ή 256) είναι μικρή. Αυτό επιτρέπει γραμμική ⁇ χρονική διαλογή αυθαίρετων ακέραιων, όχι μόνο μικρών.

Πρακτικές παρατηρήσεις στο C#

Αποτύπωμα μνήμης και μεγάλο k

Η μεγαλύτερη παγίδα είναι η κατανομή μιας σειράς καταμέτρησης μεγαλύτερη από τη διαθέσιμη μνήμη. Για παράδειγμα, η ταξινόμηση 1.000 στοιχείων με μια σειρά από 1.000.000 χώρους αποβλήτων. Πάντα να επαληθεύετε ότι [[LFT:0]]k δεν είναι τάξεις μεγέθους μεγαλύτερες από [[LFT:2]]n[[LFT:3]] ⁇ αλλιώς χρησιμοποιήστε ένα είδος σύγκρισης ή μια υβριδική προσέγγιση.

Παραλληλισμός και span< T>

Για εξαιρετικά μεγάλες συστοιχίες, μπορείτε να παραλληλοποιήσετε τη φάση καταμέτρησης χωρίζοντας την είσοδο σε κλωστές. Κάθε νήμα μετράει το τμήμα του σε μια ιδιωτική συστοιχία, και στη συνέχεια τα επιμέρους αποτελέσματα συγκεντρώνονται. Χρησιμοποιώντας και για την παραμετροσει μπορεί να μειώσει τις κατανομές σωρών όταν το εύρος είναι μικρό.

Θήκες άκρων

  • Αδειοτυπία διάταξη ⁇ επιστρέφει αμέσως.
  • Ένα στοιχείο ⁇ η διαλογή είναι ασήμαντη.
  • Όλες οι ίδιες τιμές ⁇ η σειρά καταμέτρησης έχει μία μη μηδενική είσοδο· η ανακατασκευή εκτελείται σε O(n).
  • Μεγάλη κλίμακα αλλά αραιά δεδομένα[ ⁇ Η μέτρηση Ταξινόμηση γίνεται αναποτελεσματική επειδή οι περισσότερες εγγραφές μετρούν μηδέν.

Συστάσεις επιδόσεων

Χρήση Μετρήσεων Ταξινόμηση όταν γνωρίζετε οι ακέραιοι είσοδοι εμπίπτουν σε ένα μικρό εύρος (π.χ., βαθμοί 0 ⁇ 100, ηλικίες 0 ⁇ 20, ή κώδικες σφαλμάτων 0 ⁇ 255). Για μεγαλύτερες σειρές, σκεφτείτε Radix Ταξινόμηση ή ένα υβρίδιο που πέφτει πίσω στο QuickSort για χώρισμα υψηλής εμβέλειας.

Πότε να χρησιμοποιήσετε το είδος μέτρησης (και πότε να μην)

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.

Αξιολόγηση και απόδοση

Σε ένα τυπικό σημείο αναφοράς με n = 1.000.000 και k = 1.000, η μέτρηση Ταξινόμηση ολοκληρώνεται σε περίπου 20 ⁇ 30% του χρόνου που παίρνει (που χρησιμοποιεί introsort). Το χάσμα διευρύνεται καθώς το k μειώνεται. Παρακάτω είναι μια κατά προσέγγιση σύγκριση (χρόνοι εκτέλεσης σε μια σύγχρονη CPU με .NET 8):

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

Όταν το εύρος αυξάνεται σε 10.000, η μέτρηση Ταξινόμηση εξακολουθεί να κερδίζει, αλλά το περιθώριο στενεύει. Για k = 100.000, η μνήμη πάνω από ( ⁇ 400 KB για τη σειρά καταμέτρησης) αρχίζει να βλάψει cache CPU, και η απόδοση μπορεί να υποβαθμίσει.

Συμπέρασμα

Για τους προγραμματιστές C# που ασχολούνται με μεγάλες σειρές μικρών ακέραιων, είναι ένα πολύτιμο εργαλείο που μπορεί να μειώσει δραματικά το χρόνο διαλογής. Κρατήστε ένα μάτι στο εύρος των δεδομένων σας: αν είναι μικρό και γνωστό, Μέτρησης Ταξινόμηση θα ξεπεράσει κάθε σύγκριση ⁇ βασισμένη εναλλακτική λύση. Για πιο γενική ⁇ χρήση ταξινόμηση, χρησιμοποιήστε το ενσωματωμένο ⁇ σε , αλλά πάντα να είστε έτοιμοι να πέσει στην αρίθμηση Ταξινόμηση όταν οι αριθμοί γραμμή επάνω ⁇ κυριολεκτικά και μεταφορικά.

Για περαιτέρω ανάγνωση, συμβουλευτείτε το ] άρθρο της Wikipedia σχετικά με την ταξινόμηση , το Microsoft docs on Array.Sort], και έναν πρακτικό οδηγό από GeeksforGeeks].