Come utilizzare la distribuzione ordinamento (radix ordina, ecc.) Per ordinare stringhe?

Question

So come utilizzare Radix Ordina per ordinare interi.

Ma come usarlo per ordinare stringhe?o numeri float?

Answer 1

Radix Ordina o qualsiasi altro tipo di distribuzione può essere utilizzato per ordinare i numeri del punto flottante se ignori alcune peculiarità di loro come infinito, valori non-a-number e due diverse rappresentazioni di zero. IEEE 754-2008 I numeri del punto flottanti hanno rappresentazioni binarie, compatibili nell'ordine di ordinamento con numeri interi. Quindi, se si escludono i numeri non-a-numeri e reinterpret float o double come int32 o int64, è possibile applicare direttamente qualsiasi tipo di distribuzione a loro. Modifica: I numeri del punto flottanti negativi necessitano di un trattamento speciale (come sottolineato da Ashelly), poiché il loro ordine di ordinamento è opposto all'ordine di ordinamento dei numeri interi.

Con le corde, è più difficile a causa della loro lunghezza variabile. L'altro tipo di ordinamento della distribuzione (tipo benna) può essere usato ed è spesso usato per le stringhe. Diversi caratteri di avviamento della stringa sono utilizzati per l'indicizzazione del secchio, quindi qualsiasi tipo comparativo viene utilizzato per ordinare stringhe all'interno dei secchi.

Se tutte le stringhe hanno una lunghezza quasi uguale e / o qualche tecnica viene utilizzata per amplificare le differenze tra stringhe (come descritto nel capitolo 6 di " veloce: Ricerca albero sensibile all'architettura veloce su CPU moderne e GPU "), quindi è possibile utilizzare Sort Radix: dividere la stringa a gruppi di caratteri (o Meglio, ai gruppi di bit) di uguale lunghezza, reinterpretare questi gruppi come numeri interi e continuare come se si tratta di radix ordina per interi.

Modifica: Tutti i tipi di ordinamento della distribuzione sono garantiti per funzionare correttamente solo per le stringhe ASCII. Altre codifiche di stringa possono richiedere un ordine di ordinamento diverso o può dipendere dal parametro "Collasso" della locale.

Answer 2

Sì è possibile.

Vedi radix ordina, ordinando un float dati per i galleggianti.Utilizza il fatto che i galleggianti sono stati lanciati sui tipi di integer confrontare correttamente (una volta corretti negativi per).Vedi Questo articolo per i dettagli

Per le stringhe, è possibile risolvere il problema della lunghezza variabile eseguendo un radix MSD Sort e garantendo di smettere di scendere discendenti quando si incontrano null.Vedi RADIX Ordina implementato in C ++ per String .