Java数组排序：快速的方式来获得一个数组的索引排序列表 [英] Java Array sort: Quick way to get a sorted list of indices of an array

问题描述

问题：Consder以下彩车[]：

The problem: Consder the following floats[]:

d[i] =     1.7 -0.3  2.1  0.5

我要的是一个int数组[]那些重新presents原数组索引的顺序。

What I want is an array of int[] that represents the order of the original array with indices.

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

当然，它可以用自定义的比较完成的，有序集合自定义对象，或简单地排序数组，然后寻找原始数组中的索引（战栗）。

Of course it could be done with a custom comparator, a sorted set of custom objects, or by simply sorting the array and then searching for the indices in the original array (shudder).

什么我其实找对的第二个返回参数<一等效href=\"http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/sort.html\">Matlab's排序功能。

What I am in fact looking for is the equivalent for the second return argument of Matlab's sort function.

有一个简单的方法来做到这一点（小于5 LOC）？可能会有不需要分配一个新的对象，每个元素的解决方案？

Is there an easy way to do that (<5 LOC)? May there be a solution that does not need to allocate a new object for each element?

---

更新：

感谢您的答复。不幸的是，没有一个已经提出了什么至今类似于简单而有效的解决方案我所期待的。因此，我openened一个线程在JDK反馈论坛，提出增加一个新的类库函数来解决这个问题。让我们看看太阳/ Oracle的想着这个问题。

Thanks for your responses. Unfortunately, none of what has been proposed so far resembles the simple and efficient solution I was hoping for. I therefore openened a thread in the JDK feedback forum, proposing the addition of a new class-library function to address the issue. Lets see what Sun/Oracle thinks about the issue.

<一个href=\"http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0\">http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0

推荐答案

我将定制快速排序算法的同时执行对多个阵列的交换操作：索引阵列和值数组。例如（在此基础上快速排序）：

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

这篇关于Java数组排序：快速的方式来获得一个数组的索引排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！