Ordenar matrices de tipos primitivos en orden descendente

Question

Tengo una gran variedad de tipos primitivos (dobles). ¿Cómo ordeno los elementos en orden descendente?

Desafortunadamente, la API de Java no admite la clasificación de tipos primitivos con un Comparador.

Una solución sería clasificar y luego revertir:

double[] array = new double[1048576]; 
... 
Arrays.sort(array); 
// reverse the array 
for(int i=0;i<array.length/2;i++) { 
    // swap the elements 
    double temp = array[i]; 
    array[i] = array[array.length-(i+1)]; 
    array[array.length-(i+1)] = temp; 
} 

Esto es lento - especialmente si la matriz ya está ordenada bastante bien.

¿Cuál es una mejor alternativa?

Answer 1

Java Primitive incluye funcionalidad para ordenar matrices primitivas en base a un comparador personalizado. Al usarlo, y Java 8, la muestra se puede escribir como:

double[] array = new double[1048576]; 
... 
Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false); 

Si está utilizando Maven, se puede incluir con:

<dependency> 
    <groupId>net.mintern</groupId> 
    <artifactId>primitive</artifactId> 
    <version>1.2.1</version> 
</dependency> 

Cuando se pasa false como tercer argumento a sort, utiliza una ordenación inestable, una edición simple de dual-pivot quicksort incorporada de Java. Esto significa que la velocidad debe ser similar a la de la clasificación incorporada.

La revelación completa: Escribí la biblioteca primitivos de Java.

Answer 2

Su implementación (la de la pregunta) es más rápida que, p. envolviendo con toList() y usando un método basado en comparador. El auto-boxeo y la ejecución a través de métodos de comparación u objetos de Colecciones envueltos es mucho más lento que solo invertir.

Por supuesto que puede escribir su propio tipo. Esa podría no ser la respuesta que está buscando, pero tenga en cuenta que si su comentario acerca de "si la matriz ya está bastante bien organizada" sucede con frecuencia, puede elegir un algoritmo de clasificación que maneje bien ese caso (p. Ej. inserción) en lugar de usar Arrays.sort() (que es mergesort, o inserción si la cantidad de elementos es pequeña).

Answer 3

Ha habido un poco de confusión acerca de Arrays.asList en las otras respuestas. Si dices

double[] arr = new double[]{6.0, 5.0, 11.0, 7.0}; 
List xs = Arrays.asList(arr); 
System.out.println(xs.size()); // prints 1 

entonces tendrás una lista con 1 elemento. La Lista resultante tiene la matriz doble [] como su propio elemento. Lo que quiere es tener un List<Double> cuyos elementos son los elementos del double[].

Desafortunadamente, ninguna solución que implique Comparadores funcionará para una matriz primitiva. Arrays.sort solo acepta un Comparador al pasar un Object[]. Y por los motivos descritos anteriormente, Arrays.asList no le permitirá hacer una lista de los elementos de su matriz.

Por lo tanto, a pesar de mi respuesta anterior, que los comentarios a continuación hacen referencia, no hay mejor manera que invertir manualmente la matriz después de la clasificación. Cualquier otro enfoque (como copiar los elementos en un Double[] y ordenarlos y copiarlos de vuelta) sería más código y más lento.

Answer 4

No tengo conocimiento de ninguna instalación de clasificación primitiva dentro de la API central de Java. De mis experimentos con D programming language (una especie de C en esteroides), encontré que el algoritmo de ordenación por fusión es posiblemente el algoritmo de clasificación de propósito general más rápido (es lo que el lenguaje D usa para implementar su género función).

• One implementation in Java
• Another implementation
• One more implementation

Answer 5

creo que sería mejor no volver a inventar la rueda y utilizar Arrays.sort().

Sí, vi la parte "descendente". La clasificación es la parte difícil, y desea beneficiarse de la simplicidad y velocidad del código de la biblioteca de Java. Una vez hecho esto, simplemente invierte la matriz, que es una operación O (n) relativamente barata. Here's some code he encontrado para hacer esto en tan sólo 4 líneas:

for (int left=0, right=b.length-1; left<right; left++, right--) { 
    // exchange the first and last 
    int temp = b[left]; b[left] = b[right]; b[right] = temp; 
} 

Answer 6

No puede utilizar comparadores para ordenar matrices primitivas.

Su mejor opción es poner en práctica (o pedir prestado una aplicación) de un algoritmo de ordenación que es appropriate para su caso de uso para ordenar la matriz (en orden inverso en su caso).

Answer 7

Tu algoritmo es correcto. Pero podemos hacer la optimización de la siguiente manera: Mientras invierte, puede intentar mantener otra variable para reducir el contador retroactivo, ¡ya que la computación de array.length- (i + 1) puede tomar tiempo! Y también mover declaración de la temperatura exterior, de modo que cada vez que no es necesario asignar

double temp; 

for(int i=0,j=array.length-1; i < (array.length/2); i++, j--) { 

    // swap the elements 
    temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

Answer 8

double[] array = new double[1048576]; 

...

Por orden predeterminado es ascendente

Para invertir el orden

Arrays.sort(array,Collections.reverseOrder()); 

Answer 9

Si el rendimiento es importante, y la lista por lo general ya está ordenado bastante bien

El ordenamiento de burbuja debería ser una de las formas más lentas de clasificación, pero he visto casos en los que el mejor rendimiento fue una clasificación de burbuja bidireccional simple.

Este puede ser uno de los pocos casos en los que puede beneficiarse al codificarlo usted mismo. Pero realmente debe hacerlo bien (asegúrese de que al menos alguien más confirme su código, compruebe que funciona, etc.)

Como alguien más señaló, puede ser incluso mejor comenzar con una matriz ordenada, y mantenlo ordenado mientras cambias los contenidos. Eso puede funcionar aún mejor.

Answer 10

Guava tiene métodos para convertir matrices primitivas en Listas de tipos de envoltura. Lo bueno es que estas listas son vistas en vivo, por lo que las operaciones en ellas también funcionan en las matrices subyacentes (similar a Arrays.asList(), pero para las primitivas).

De todos modos, cada una de estas listas puede ser pasado a Collections.reverse():

int[] intArr = { 1, 2, 3, 4, 5 }; 
float[] floatArr = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f }; 
double[] doubleArr = { 1.0d, 2.0d, 3.0d, 4.0d, 5.0d }; 
byte[] byteArr = { 1, 2, 3, 4, 5 }; 
short[] shortArr = { 1, 2, 3, 4, 5 }; 
Collections.reverse(Ints.asList(intArr)); 
Collections.reverse(Floats.asList(floatArr)); 
Collections.reverse(Doubles.asList(doubleArr)); 
Collections.reverse(Bytes.asList(byteArr)); 
Collections.reverse(Shorts.asList(shortArr)); 
System.out.println(Arrays.toString(intArr)); 
System.out.println(Arrays.toString(floatArr)); 
System.out.println(Arrays.toString(doubleArr)); 
System.out.println(Arrays.toString(byteArr)); 
System.out.println(Arrays.toString(shortArr)); 

de salida:

[5, 4, 3, 2, 1]
[5,0, 4,0, 3,0 , 2,0, 1,0]
[5,0, 4,0, 3,0, 2,0, 1,0]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

Answer 11

Double[] d = {5.5, 1.3, 8.8}; 
Arrays.sort(d, Collections.reverseOrder()); 
System.out.println(Arrays.toString(d)); 

Collections.reverseOrder() no funciona en primitivas, pero Double, Integer etc. funciona con colecciones.reverseOrder()

Answer 12

Con los tipos numéricos, negando los elementos antes y después de clase parece una opción. La velocidad relativa a una sola marcha atrás después de la clasificación depende de la caché, y si el retroceso no es más rápido, cualquier diferencia puede perderse en el ruido.

Answer 13

creo que la solución más fácil todavía:

1. Conseguir el orden natural de la matriz
2. Encontrar el máximo dentro de esa matriz ordenada que es entonces el último elemento
3. El uso de un bucle for con operador de decremento

Como dijeron otros antes: usar toList es un esfuerzo adicional, Arrays.sort (array, Collections.reverseOrder()) no funciona con primitivos y usa un fram adicional ework parece demasiado complicado cuando todo lo que necesita es ya inbuild y por lo tanto probablemente más rápido, así ... código

muestra:

import java.util.Arrays; 

public class SimpleDescending { 

    public static void main(String[] args) { 

     // unsorted array 
     int[] integerList = {55, 44, 33, 88, 99}; 

     // Getting the natural (ascending) order of the array 
     Arrays.sort(integerList); 

     // Getting the last item of the now sorted array (which represents the maximum, in other words: highest number) 
     int max = integerList.length-1; 

     // reversing the order with a simple for-loop 
     System.out.println("Array in descending order:"); 
     for(int i=max; i>=0; i--) { 
      System.out.println(integerList[i]); 
     } 

     // You could make the code even shorter skipping the variable max and use 
     // "int i=integerList.length-1" instead of int "i=max" in the parentheses of the for-loop 
    } 
} 

Answer 14

para las pequeñas matrices esto puede funcionar.

int getOrder (double num, double[] array){ 
    double[] b = new double[array.length]; 
    for (int i = 0; i < array.length; i++){ 
     b[i] = array[i]; 
    } 
    Arrays.sort(b); 
    for (int i = 0; i < b.length; i++){ 
     if (num < b[i]) return i; 
    } 
    return b.length; 
} 

Me sorprendió que la carga inicial de la matriz b era necesario

double[] b = array; // makes b point to array. so beware! 

Answer 15

Before sorting the given array multiply each element by -1 

a continuación, utilizar Arrays.sort (arr), de nuevo multiplicar cada elemento por -1

for(int i=0;i<arr.length;i++) 
    arr[i]=-arr[i]; 
Arrays.sort(arr); 
for(int i=0;i<arr.length;i++) 
    arr[i]=-arr[i]; 

Answer 16

Si usa java8, simplemente convierta la matriz en transmisión, ordene y convierta de nuevo. Todas las tareas se pueden hacer solo en una línea, así que siento que no es tan malo.

double[] nums = Arrays.stream(nums).boxed(). 
     .sorted((i1, i2) -> Double.compare(i2, i1)) 
     .mapToDouble(Double::doubleValue) 
     .toArray(); 

Answer 17

A continuación, presento mi solución, usted puede adaptarlo a sus necesidades.

¿Cómo funciona? Toma una matriz de enteros como argumentos. Después de eso, creará una nueva matriz que contendrá los mismos valores que la matriz de los argumentos. La razón de hacer esto es dejar la matriz original intacta.

Una vez que la nueva matriz contiene los datos copiados, clasificamos que mediante el canje de los valores hasta que la condición si (newArr [i] < newArr [i + 1]) se evalúa como falsa. Eso significa que la matriz está ordenada en orden descendente.

Para una explicación detallada, consulte la publicación de mi blog here.

public static int[] sortDescending(int[] array) 
{ 
    int[] newArr = new int[array.length]; 

    for(int i = 0; i < array.length; i++) 
    { 
     newArr[i] = array[i]; 
    } 

    boolean flag = true; 
    int tempValue; 

    while(flag) 
    { 
     flag = false; 

     for(int i = 0; i < newArr.length - 1; i++) 
     { 
      if(newArr[i] < newArr[i+1]) 
      { 
       tempValue = newArr[i]; 
       newArr[i] = newArr[i+1]; 
       newArr[i+1] = tempValue; 
       flag = true; 
      } 
     } 
    } 

    return newArr; 
} 

Answer 18

Un enfoque mejor y más concisa podría ser:

Arrays.sort(array); 
List<Integer> list=Arrays.asList(array); 
Collections.reverse(list); 
System.out.println(list); 

Esto daría a la matriz invertida y es más presentable. Entrada: 4 2 9 5 3 Salida: [9, 5, 4, 3, 2]