Tri de tableau Java: moyen rapide d'obtenir une liste triée des index d'un tableau

Question

Le problème: Consder la suite de flotteurs[]:

d[i] =     1.7 -0.3  2.1  0.5

Ce que je veux, c'est un tableau de int[] qui représente l'ordre du tableau original avec des indices.

s[i] =       1    3    0    2
d[s[i]] = -0.3  0.5  1.7  2.1

Bien sûr, il pourrait être fait avec un comparateur, un ensemble trié des objets personnalisés, ou tout simplement en triant le tableau et ensuite chercher les indices dans le tableau d'origine (frisson).

Ce que je suis en fait à la recherche est l'équivalent pour le second retour de l'argument de Matlab la fonction de tri.

Est-il un moyen facile de le faire (<5 LOC)? Peut-il y avoir une solution qui n'a pas besoin d'allouer un nouvel objet pour chaque élément?

---

Mise à jour:

Merci pour vos réponses. Malheureusement, rien de ce qui a été proposé jusqu'à présent ressemble à la solution simple et efficace, j'espérais. J'ai donc openened un thread dans le JDK commentaires du forum, en proposant l'ajout d'une nouvelle classe-fonction de la bibliothèque pour résoudre le problème. Permet de voir ce que Sun/Oracle pense de la question.

http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0

Answer 1

Solution simple pour créer un tableau d'indexation: triez l'indexeur en comparant les valeurs de données:

 final Integer[] idx = { 0, 1, 2, 3 };
final float[] data = { 1.7f, -0.3f,  2.1f,  0.5f };

Arrays.sort(idx, new Comparator<Integer>() {
    @Override public int compare(final Integer o1, final Integer o2) {
        return Float.compare(data[o1], data[o2]);
    }
});
 

Answer 2

Créer un TreeMap de valeurs pour les indices

    float[] array = new float[]{};
    Map<Float, Integer> map = new TreeMap<Float, Integer>();
    for (int i = 0; i < array.length; ++i) {
        map.put(array[i], i);
    }
    Collection<Integer> indices = map.values();

les indices seront triées par les flotteurs ils point, le tableau d'origine est intacte. La conversion de l' Collection<Integer> d'un int[] est laissé comme exercice si c'est vraiment nécessaire.

EDIT: Comme indiqué dans les commentaires, cette approche ne fonctionne pas si il y a des valeurs en double dans le flotteur tableau. Ce problème peut être réglé en faisant l' Map<Float, Integer> en Map<Float, List<Integer>> bien que cela va compliquer l'intérieur de la boucle for et la génération de la dernière collection légèrement.

Answer 3

Je voudrais adapter l'algorithme quicksort pour effectuer l'opération d'échange sur plusieurs tableaux en même temps: le tableau d'index et le tableau de valeurs. Par exemple (basé sur ce tri rapide ):

 public static void quicksort(float[] main, int[] index) {
    quicksort(main, index, 0, index.length - 1);
}

// quicksort a[left] to a[right]
public static void quicksort(float[] a, int[] index, int left, int right) {
    if (right <= left) return;
    int i = partition(a, index, left, right);
    quicksort(a, index, left, i-1);
    quicksort(a, index, i+1, right);
}

// partition a[left] to a[right], assumes left < right
private static int partition(float[] a, int[] index, 
int left, int right) {
    int i = left - 1;
    int j = right;
    while (true) {
        while (less(a[++i], a[right]))      // find item on left to swap
            ;                               // a[right] acts as sentinel
        while (less(a[right], a[--j]))      // find item on right to swap
            if (j == left) break;           // don't go out-of-bounds
        if (i >= j) break;                  // check if pointers cross
        exch(a, index, i, j);               // swap two elements into place
    }
    exch(a, index, i, right);               // swap with partition element
    return i;
}

// is x < y ?
private static boolean less(float x, float y) {
    return (x < y);
}

// exchange a[i] and a[j]
private static void exch(float[] a, int[] index, int i, int j) {
    float swap = a[i];
    a[i] = a[j];
    a[j] = swap;
    int b = index[i];
    index[i] = index[j];
    index[j] = b;
}
 

Answer 4

Avec Java fonctionnel :

 import static fj.data.Array.array;
import static fj.pre.Ord.*;
import fj.P2;

array(d).toStream().zipIndex().qSort(p2Ord(doubleOrd, intOrd))
  .map(P2.<Double, Integer>__2()).toArray();
 

Answer 5

Le cas plus général de la réponse de Jherico qui autorise les doublons serait le suivant:

 // Assuming you've got: float[] array; defined already

TreeMap<Float, List<Integer>> map = new TreeMap<Float, List<Integer>>();
for(int i = 0; i < array.length; i++) {
    List<Integer> ind = map.get(array[i]);
    if(ind == null){
        ind = new ArrayList<Integer>();
        map.put(array[i], ind);
    }
    ind.add(i);
}

// Now flatten the list
List<Integer> indices = new ArrayList<Integer>();
for(List<Integer> arr : map.values()) {
    indices.addAll(arr);
}