Java Array sort: Quick way to get a sorted list of indices of an array

I would tailor the quicksort algorithm to perform the exchange operation on multiple arrays at the same time: the index array and the value array. For example (based on this 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;
}

Create a TreeMap of values to 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();

indices will be the sorted by the floats they point to, the original array is untouched. Converting the Collection<Integer> to a int[] is left as an exercise if it's really necessary.

EDIT: As noted in the comments, this approach does not work if there are duplicate values in the float array. This can be addressed by making the Map<Float, Integer> into a Map<Float, List<Integer>> though this will complicate the inside of the for loop and the generation of the final collection slightly.

With Functional Java:

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

The more general case of Jherico's answer that allows duplicate values would be this:

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

Simple solution to create an indexer array: sort the indexer comparing the data values:

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

I guess the easiest way to do it is to index the array as it is created. You would need key,value pairs. If the index is a separate structure, then i cant see how you could do it without other objects (interested in seeing it though)

Convert the input to a pair class like the one below and then sort this using Arrays.sort(). Arrays.sort() ensures that original order is preserved for equal values like Matlab does. You then need to convert the sorted result back to the separate arrays.

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

}