Java Array Sort: modo veloce per ottenere una lista ordinata di indici di un array

Question

Il problema: Consder i seguenti carri []:

d[i] =  1.7 -0.3 2.1 0.5 

Quello che voglio è un array di int [] che rappresenta l'ordine della matrice originale con indici.

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

Ovviamente potrebbe essere fatto con un comparatore personalizzato, un insieme ordinato di oggetti personalizzati, o semplicemente smistamento della matrice e quindi cercare gli indici dell'array originale (brivido).

Quello che sto cercando è l'equivalente per il secondo argomento di ritorno di Matlab's sort function.

C'è un modo semplice per farlo (< 5 LOC)? Può esserci una soluzione che non ha bisogno di allocare un nuovo oggetto per ogni elemento?

---

Aggiornamento:

Grazie per le vostre risposte. Sfortunatamente, nessuno di ciò che è stato proposto finora assomiglia alla soluzione semplice ed efficiente che speravo. Ho quindi aperto un thread nel forum di feedback JDK, proponendo l'aggiunta di una nuova funzione di libreria di classi per risolvere il problema. Vediamo cosa pensa Sun/Oracle del problema.

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

Answer 1

avrei adattare l'algoritmo quicksort per eseguire l'operazione di scambio su più array allo stesso tempo: l'array indice e schiera di valori.Per esempio (sulla base di questo quicksort):

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 2

Credo che il modo più semplice per farlo è quello di indice di matrice in quanto è creato. Avresti bisogno di coppie chiave, valore. Se l'indice è una struttura separata, quindi non posso vedere come si potrebbe fare senza gli altri oggetti (interessato a vedere però)

Answer 3

Creare un TreeMap di valori agli indici

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(); 

indici saranno l'ordinati dai galleggianti a cui puntano, l'array originale è intatto. La conversione di Collection<Integer> in un int[] viene lasciata come esercizio se è davvero necessaria.

MODIFICA: Come indicato nei commenti, questo approccio non funziona se ci sono valori duplicati nell'array float. Questo può essere risolto rendendo lo Map<Float, Integer> in un Map<Float, List<Integer>> anche se questo complicherà leggermente l'interno del ciclo for e la generazione della raccolta finale.

Answer 4

Con Functional Java:

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

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

Answer 5

Converti l'ingresso ad una classe coppia come quella qui sotto e poi ordinare questo using Arrays.sort(). Arrays.sort() garantisce che l'ordine originale venga mantenuto per valori uguali come fa Matlab. È quindi necessario convertire il risultato ordinato in array separati.

class SortPair implements Comparable<SortPair> 
{ 
    private int originalIndex; 
    private double value; 

    public SortPair(double value, int originalIndex) 
    { 
    this.value = value; 
    this.originalIndex = originalIndex; 
    } 

    @Override public int compareTo(SortPair o) 
    { 
    return Double.compare(value, o.getValue()); 
    } 

    public int getOriginalIndex() 
    { 
    return originalIndex; 
    } 

    public double getValue() 
    { 
    return value; 
    } 

}

Answer 6

Il caso più generale di Jherico's answer che consente valori duplicati sarebbe questo:

// 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); 
} 

Answer 7

soluzione semplice per creare un array indicizzatore: ordinare l'indicizzatore confrontando il valori dei dati:

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 8

Un'altra soluzione non semplice. Ecco una versione di merge sort che è stable e non modifica l'array sorgente, sebbene l'unione richieda memoria extra.

public static int[] sortedIndices(double[] x) { 
    int[] ix = new int[x.length]; 
    int[] scratch = new int[x.length]; 
    for (int i = 0; i < ix.length; i++) { 
     ix[i] = i; 
    } 
    mergeSortIndexed(x, ix, scratch, 0, x.length - 1); 
    return ix; 
} 

private static void mergeSortIndexed(double[] x, int[] ix, int[] scratch, int lo, int hi) { 
    if (lo == hi) 
     return; 
    int mid = (lo + hi + 1)/2; 
    mergeSortIndexed(x, ix, scratch, lo, mid - 1); 
    mergeSortIndexed(x, ix, scratch, mid, hi); 
    mergeIndexed(x, ix, scratch, lo, mid - 1, mid, hi); 
} 

private static void mergeIndexed(double[] x, int[] ix, int[] scratch, int lo1, int hi1, int lo2, int hi2) { 
    int i = 0; 
    int i1 = lo1; 
    int i2 = lo2; 
    int n1 = hi1 - lo1 + 1; 
    while (i1 <= hi1 && i2 <= hi2) { 
     if (x[ix[i1]] <= x[ix[i2]]) 
      scratch[i++] = ix[i1++]; 
     else 
      scratch[i++] = ix[i2++]; 
    } 
    while (i1 <= hi1) 
     scratch[i++] = ix[i1++]; 
    while (i2 <= hi2) 
     scratch[i++] = ix[i2++]; 
    for (int j = lo1; j <= hi1; j++) 
     ix[j] = scratch[j - lo1]; 
    for (int j = lo2; j <= hi2; j++) 
     ix[j] = scratch[(j - lo2 + n1)]; 
} 

Answer 9

La soluzione migliore sarebbe lungo le linee di qsort di C, che consente di specificare le funzioni per confrontare e scambiare, in modo da qsort bisogno di non essere a conoscenza del tipo o di organizzazione dei dati da ordinare. Eccone uno che puoi provare. Poiché Java non ha funzioni, utilizzare la classe interna Array per avvolgere l'array o la raccolta da ordinare. Quindi avvolgilo in un IndexArray e ordina. Il risultato di getIndex() su IndexArray sarà un array di indici come descritto in JavaDoc.

public class QuickSortArray { 

public interface Array { 
    int cmp(int aindex, int bindex); 
    void swap(int aindex, int bindex); 
    int length(); 
} 

public static void quicksort(Array a) { 
    quicksort(a, 0, a.length() - 1); 
} 

public static void quicksort(Array a, int left, int right) { 
    if (right <= left) return; 
    int i = partition(a, left, right); 
    quicksort(a, left, i-1); 
    quicksort(a, i+1, right); 
} 

public static boolean isSorted(Array a) { 
    for (int i = 1, n = a.length(); i < n; i++) { 
     if (a.cmp(i-1, i) > 0) 
      return false; 
    } 
    return true; 
} 

private static int mid(Array a, int left, int right) { 
    // "sort" three elements and take the middle one 
    int i = left; 
    int j = (left + right)/2; 
    int k = right; 
    // order the first two 
    int cmp = a.cmp(i, j); 
    if (cmp > 0) { 
     int tmp = j; 
     j = i; 
     i = tmp; 
    } 
    // bubble the third down 
    cmp = a.cmp(j, k); 
    if (cmp > 0) { 
     cmp = a.cmp(i, k); 
     if (cmp > 0) 
      return i; 
     return k; 
    } 
    return j; 
} 

private static int partition(Array a, int left, int right) { 
    int mid = mid(a, left, right); 
    a.swap(right, mid); 
    int i = left - 1; 
    int j = right; 

    while (true) { 
     while (a.cmp(++i, right) < 0) 
      ; 
     while (a.cmp(right, --j) < 0) 
      if (j == left) break; 
     if (i >= j) break; 
     a.swap(i, j); 
    } 
    a.swap(i, right); 
    return i; 
} 

public static class IndexArray implements Array { 
    int[] index; 
    Array a; 

    public IndexArray(Array a) { 
     this.a = a; 
     index = new int[a.length()]; 
     for (int i = 0; i < a.length(); i++) 
      index[i] = i; 
    } 

    /** 
    * Return the index after the IndexArray is sorted. 
    * The nested Array is unsorted. Assume the name of 
    * its underlying array is a. The returned index array 
    * is such that a[index[i-1]] <= a[index[i]] for all i 
    * in 1..a.length-1. 
    */ 
    public int[] index() { 
     int i = 0; 
     int j = index.length - 1; 
     while (i < j) { 
      int tmp = index[i]; 
      index[i++] = index[j]; 
      index[j--] = tmp; 
     } 
     int[] tmp = index; 
     index = null; 
     return tmp; 
    } 

    @Override 
    public int cmp(int aindex, int bindex) { 
     return a.cmp(index[aindex], index[bindex]); 
    } 

    @Override 
    public void swap(int aindex, int bindex) { 
     int tmp = index[aindex]; 
     index[aindex] = index[bindex]; 
     index[bindex] = tmp; 
    } 

    @Override 
    public int length() { 
     return a.length(); 
    } 

} 

Answer 10

//Here index array(of length equal to length of d array) contains the numbers from 0 to length of d array 
     public static Integer [] SortWithIndex(float[] data, Integer [] index) 
    { 
    int len = data.length; 
    float temp1[] = new float[len]; 
    int temp2[] = new int[len]; 



     for (int i = 0; i <len; i++) { 


       for (int j = i + 1; j < len; j++) { 


        if(data[i]>data[j]) 
        { 
        temp1[i] = data[i]; 
        data[i] = data[j]; 
        data[j] = temp1[i]; 



        temp2[i] = index[i]; 
        index[i] = index[j]; 
        index[j] = temp2[i]; 

        } 
        } 

     } 

     return index; 

    } 

Answer 11

public static int[] indexSort(final double[] v, boolean keepUnsorted) { 
    final Integer[] II = new Integer[v.length]; 
    for (int i = 0; i < v.length; i++) II[i] = i; 
    Arrays.sort(II, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return Double.compare(v[o1],v[o2]); 
     } 
    }); 
    int[] ii = new int[v.length]; 
    for (int i = 0; i < v.length; i++) ii[i] = II[i]; 
    if (!keepUnsorted) { 
     double[] clon = v.clone(); 
     for (int i = 0; i < v.length; i++) v[i] = clon[II[i]]; 
    } 
    return ii; 
} 

Answer 12

vorrei fare qualcosa di simile:

public class SortedArray<T extends Comparable<T>> { 
    private final T[] tArray; 
    private final ArrayList<Entry> entries; 

    public class Entry implements Comparable<Entry> { 
     public int index; 

     public Entry(int index) { 
      super(); 
      this.index = index; 
     } 

     @Override 
     public int compareTo(Entry o) { 
      return tArray[index].compareTo(tArray[o.index]); 
     } 
    } 

    public SortedArray(T[] array) { 
     tArray = array; 
     entries = new ArrayList<Entry>(array.length); 
     for (int i = 0; i < array.length; i++) { 
      entries.add(new Entry(i)); 
     } 
     Collections.sort(entries); 
    } 

    public T getSorted(int i) { 
     return tArray[entries.get(i).index]; 

    } 

    public T get(int i) { 
     return tArray[i]; 
    } 
} 

Answer 13

Qui di seguito è un metodo basato sulla inserimento Ordina

public static int[] insertionSort(float[] arr){ 
    int[] indices = new int[arr.length]; 
     indices[0] = 0; 
     for(int i=1;i<arr.length;i++){ 
      int j=i; 
      for(;j>=1 && arr[j]<arr[j-1];j--){ 
        float temp = arr[j]; 
        arr[j] = arr[j-1]; 
        indices[j]=indices[j-1]; 
        arr[j-1] = temp; 
      } 
      indices[j]=i; 
     } 
     return indices;//indices of sorted elements 
} 

Answer 14

Utilizzo di Java 8 caratteristiche (senza libreria extra), modo conciso per raggiungerlo.

int[] a = {1,6,2,7,8} 
int[] sortedIndices = IntStream.range(0, a.length) 
       .boxed().sorted((i, j) -> a[i] - a[j]) 
       .mapToInt(ele -> ele).toArray(); 

Answer 15

Mi piacerebbe usare questo perché è molto fast.But lo uso per int, si può cambiare a stare a galla.

private static void mergeSort(int[]array,int[] indexes,int start,int end){ 
    if(start>=end)return; 
    int middle = (end-start)/2+start; 
    mergeSort(array,indexes,start,middle); 
    mergeSort(array,indexes,middle+1,end); 
    merge(array,indexes,start,middle,end); 
} 
private static void merge(int[]array,int[] indexes,int start,int middle,int end){ 
    int len1 = middle-start+1; 
    int len2 = end - middle; 
    int leftArray[] = new int[len1]; 
    int leftIndex[] = new int[len1]; 
    int rightArray[] = new int[len2]; 
    int rightIndex[] = new int[len2]; 
    for(int i=0;i<len1;++i)leftArray[i] = array[i+start]; 
    for(int i=0;i<len1;++i)leftIndex[i] = indexes[i+start]; 
    for(int i=0;i<len2;++i)rightArray[i] = array[i+middle+1]; 
    for(int i=0;i<len2;++i)rightIndex[i] = indexes[i+middle+1]; 
    //merge 
    int i=0,j=0,k=start; 
    while(i<len1&&j<len2){ 
     if(leftArray[i]<rightArray[j]){ 
      array[k] = leftArray[i]; 
      indexes[k] = leftIndex[i]; 
      ++i; 
     } 
     else{ 
      array[k] = rightArray[j]; 
      indexes[k] = rightIndex[j]; 
      ++j; 
     } 
     ++k; 
    } 
    while(i<len1){ 
     array[k] = leftArray[i]; 
     indexes[k] = leftIndex[i]; 
     ++i;++k; 
    } 
    while(j<len2){ 
     array[k] = rightArray[j]; 
     indexes[k] = rightIndex[j]; 
     ++j;++k; 
    } 
}