Java数组排序:快速获取数组索引的排序列表

Question

问题:考虑以下浮点数[]:

d[i] =     1.7 -0.3  2.1  0.5

我想要的是一个int []数组,它表示带索引的原始数组的顺序.

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

当然,可以使用自定义比较器,自定义对象的排序集,或者通过简单地对数组进行排序,然后搜索原始数组中的索引(颤抖)来完成.

我实际上正在寻找的是Matlab的sort函数的第二个返回参数的等价物.

有没有一种简单的方法(<5 LOC)？可能有一个解决方案,不需要为每个元素分配一个新对象？

---

更新:

谢谢你的回复.不幸的是,迄今为止提出的所有内容都不像我希望的简单而有效的解决方案.因此,我在JDK反馈论坛中打开了一个帖子,建议添加一个新的类库函数来解决这个问题.让我们看看Sun/Oracle对此问题的看法.

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

Answer 1

创建索引器数组的简单解决方案:对索引器进行排序,比较数据值:

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

TreeMap为索引创建值

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

索引将按它们指向的浮点数排序,原始数组不受影响.如果真的有必要,将其转换Collection<Integer>为a int[]作为练习.

编辑:如评论中所述,如果float数组中存在重复值,则此方法不起作用.这可以通过使Map<Float, Integer>a成为一个Map<Float, List<Integer>>虽然这将使for循环的内部和最终集合的生成稍微复杂化来解决.

Answer 3

我将定制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 4

使用Java 8功能(没有额外的库),实现它的简洁方法.

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 5

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