El problema es que tengo una lista de 1 millón de números, pero solo quiero los 10 primeros de la lista ordenada, pero no quiero clasificar toda la lista? ¿Es eso posible?Cómo obtener los primeros 10 elementos ordenados de una lista sin ordenar toda la lista
Sí. Simplemente revisa la lista una vez y almacena los diez números más pequeños. El algoritmo será O (n) (en realidad, O (n * 10) en el peor caso)
Foreach (list)
- Check if current item is smaller than the biggest item in the sorted Array[10]
- If so, put the current item at the right spot (sorted) in the array (insertionsort), bumping away the biggest item.
Lo que queremos es una cola de prioridad. Inserta cada número en una cola de prioridad. Si el tamaño de la cola excede de 10, elimine el valor más pequeño (o el más grande). Los valores que permanecen en la cola al final son los 10 más grandes (o los más pequeños).
Si la cola se implementa utilizando un Heap, este puede ser un algoritmo muy eficaz.
Puede convertir ese 10 en una constante basada en lg usando un montón para su "lista" de 10. :-) – corsiKa
O (n * 10) = O (n). – recursive
recursivo: por supuesto, pero esto deja en claro que cuando el número 10 sea más alto (digamos, usted quiere que la mitad de la lista esté ordenada), la O cambiará, y una matriz simple no funcionará. Entonces necesitarás una mejor estructura de datos como dijo el glowcoder. – Konerak