Java 数组排序：快速获取数组索引的排序列表的方法

Question

问题：考虑以下 float[]：

 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 的排序函数 的第二个返回参数的等价物。

有没有一种简单的方法可以做到这一点（ LOC）？可能有一种解决方案不需要为每个元素分配一个新对象吗？

---

更新：

感谢您的回复。不幸的是，到目前为止所提出的方案都与我所希望的简单有效的解决方案相似。因此，我在 JDK 反馈论坛中开了一个帖子，提议添加一个新的类库函数来解决这个问题。让我们看看 Sun/Oracle 对这个问题的看法。

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

原文由 edgar.holleis 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我会定制快速排序算法以同时对多个数组执行交换操作：索引数组和值数组。例如（基于这个 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;
}

原文由 akarnokd 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

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

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

原文由 carloscs 发布，翻译遵循 CC BY-SA 2.5 许可协议