algorithm
Conteggio Sort
Ricerca…
Conteggio Ordina informazioni di base
L'ordinamento di conteggio è un algoritmo di ordinamento intero per una raccolta di oggetti che ordina in base alle chiavi degli oggetti.
passi
- Costruisce un array di lavoro C che ha dimensione uguale all'intervallo dell'array di input A.
- Scorrere fino a A , assegnando C [x] in base al numero di volte in cui X è apparso in A.
- Trasforma C in un array in cui C [x] fa riferimento al numero di valori ≤ x eseguendo un'iterazione attraverso la matrice, assegnando a ciascuna C [x] la somma del suo valore precedente e tutti i valori in C che precedono.
- Iterate all'indietro attraverso A , ponendo ogni valore in un nuovo array ordinato B all'indice registrato in C. Questo viene fatto per un dato A [x] assegnando B [ C [ A [x]]] a A [x] e decrementando C [ A [x]] nel caso in cui ci fossero valori duplicati nell'array originale non ordinato.
Esempio di ordinamento di conteggio
Spazio ausiliario: O(n+k)
Complessità temporale: peggiore: O(n+k)
, Best-case: O(n)
, caso medio O(n+k)
Implementazione di Psuedocode
vincoli:
- Input (una matrice da ordinare)
- Numero di elementi in input (n)
- Chiavi nell'intervallo 0..k-1 (k)
- Conta (una serie di numeri)
pseudocodice:
for x in input:
count[key(x)] += 1
total = 0
for i in range(k):
oldCount = count[i]
count[i] = total
total += oldCount
for x in input:
output[count[key(x)]] = x
count[key(x)] += 1
return output
Implementazione C #
public class CountingSort
{
public static void SortCounting(int[] input, int min, int max)
{
var count = new int[max - min + 1];
var z = 0;
for (var i = 0; i < count.Length; i++)
count[i] = 0;
foreach (int i in input)
count[i - min]++;
for (var i = min; i <= max; i++)
{
while (count[i - min]-- > 0)
{
input[z] = i;
++z;
}
}
}
public static int[] Main(int[] input)
{
SortCounting(input, input.Min(), input.Max());
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow