Esta es una pregunta de tareas, por lo que me gustaría evitar las respuestas completas y preferiría sugerencias si es posible.Algún algoritmo de ordenación de O (n)
Dada una matriz de enteros aleatorios A [1 ... x], el programa debe devolver los primeros elementos de la matriz y en orden creciente donde 1 < = y < = sqrt (x). Entonces, básicamente, dado un conjunto [5,9,2,8] ey = 2, el programa debería devolver [2,5].
La respuesta "ordenar primero, devolver primero y elementos" está fuera de la ventana ya que lo mejor que podemos hacer es n * tiempo de logn con merge o quicksort. La respuesta tiene que hacer uso del hecho de que solo devolvemos la mayoría de los elementos sqrt (x), y la única otra respuesta que tengo hasta ahora es hacer una búsqueda for-loop para el elemento mínimo en la matriz, eliminando el mínimo de la matriz, guardándolo en una nueva matriz, digamos B, y repetir el proceso en la versión ahora más pequeña modificada de una de largo x-1, lo que nos da el tiempo de funcionamiento de esta manera:
x + (x-1) + (x-2) + ... + (x-y)
que cuenta el número de iteración for-loop de min-search, y nos da como máximo iteraciones y o sqrt (x) en el peor de los casos, y hay como máximo x elementos en la matriz. Así que tenemos sqrt (x) * x, que es mejor que O (n * logn) pero todavía no del todo O (n): /.
¿Ha mirado a [clasificación del cubo] (http://en.wikipedia.org/wiki/Bucket_sort)? Cuando veo los requisitos O (n), es lo único que me viene a la mente. –
"el programa debe devolver los primeros y * dígitos *". Tal vez * números *? – ruslik
@ruslki - sí, quise decir los primeros elementos de la matriz. Arreglando eso ahora. – thezhaba