¿Cómo utilizar la clasificación por distribución (clasificación por base, etc.) para ordenar cadenas?

Question

Sé cómo usar la clasificación por base para ordenar números enteros.

¿Pero cómo usarlo para ordenar cadenas?o números flotantes?

Answer 1

La clasificación por base o cualquier otra clasificación de distribución se puede utilizar para ordenar números de punto flotante si se ignoran algunas peculiaridades de ellos, como el infinito, los valores que no son un número y dos representaciones diferentes de cero. IEEE 754-2008 Los números de coma flotante tienen representaciones binarias, compatibles en orden de clasificación con los números enteros.Entonces, si excluyes los números que no son números y reinterpretas float o double como int32 o int64, puede aplicarles directamente cualquier tipo de distribución. Editar: Los números de coma flotante negativos necesitan un tratamiento especial (como lo señala AShelly), porque su orden de clasificación es opuesto al orden de clasificación de los números enteros.

Con las cuerdas es más difícil debido a su longitud variable.Se puede utilizar otro tipo de clasificación de distribución (clasificación por cubos), que suele utilizarse para cadenas.Se utilizan varios caracteres iniciales de la cadena para la indexación de depósitos, luego se utiliza cualquier clasificación comparativa para ordenar cadenas dentro de los depósitos.

Si todas las cuerdas tienen casi la misma longitud y/o se utiliza alguna técnica para amplificar las diferencias entre cuerdas (como se describe en el capítulo 6 de "RÁPIDO:Búsqueda rápida de árboles sensibles a la arquitectura en CPU y GPU modernas"), entonces también se puede utilizar la clasificación por base:divida la cadena en grupos de caracteres (o mejor, en grupos de bits) de igual longitud, reinterprete estos grupos como números enteros y continúe como si fuera una ordenación por base para números enteros.

Editar: Se garantiza que todos los tipos de clasificación de distribución funcionarán correctamente solo para cadenas ASCII.Otras codificaciones de cadenas pueden requerir un orden de clasificación diferente o pueden depender del parámetro "intercalar" de la configuración regional.

Answer 2

Sí, es posible.

Consulte Radix Sort, Ordenando un flotador de datos para flotadores.Utiliza el hecho de que los flotadores emiten a los tipos de enteros se comparan correctamente (una vez que se corrijan los negativos).Consultela este artículo para más detalles

Para cadenas, puede resolver el problema de la longitud de la variable haciendo una especie de MSD Radix y asegurando que deje de descender cuando se encuentra con NULLS.Consulte Radix Ordenar implementado en C ++ para cadena .