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

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

提问by edgar.holleis

The problem: Consider the following floats[]:

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

d[i] =     1.7 -0.3  2.1  0.5

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

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

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).

当然，它可以通过自定义比较器、一组排序的自定义对象或通过简单地对数组进行排序然后在原始数组中搜索索引来完成（不寒而栗）。

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

我实际上正在寻找的是Matlab 排序函数的第二个返回参数的等效项。

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?

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

---

---

Update:

更新：

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.

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

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

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

采纳答案by akarnokd

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):

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

回答by Tom

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)

我想最简单的方法是在创建数组时对其进行索引。您将需要键值对。如果索引是一个单独的结构，那么我看不到没有其他对象如何做到这一点（尽管有兴趣看到它）

回答by Jherico

Create a TreeMapof values to indices

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

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.

索引将按它们指向的浮点数排序，原始数组不变。如果真的有必要，将 the 转换Collection<Integer>为 a留作int[]练习。

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.

编辑：如评论中所述，如果浮点数组中存在重复值，则此方法不起作用。这可以通过将 inMap<Float, Integer>变成 a来解决，Map<Float, List<Integer>>但这会使 for 循环内部和最终集合的生成稍微复杂化。

回答by Apocalisp

With Functional Java:

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

回答by Mark

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.

将输入转换为如下所示的配对类，然后使用 Arrays.sort() 对其进行排序。Arrays.sort() 确保像 Matlab 一样为相等的值保留原始顺序。然后，您需要将排序结果转换回单独的数组。

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

}

}

回答by Mark Elliot

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

允许重复值的Jherico 答案的更一般情况是：

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

回答by carloscs

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

回答by xan

Another non-simple solution. Here's a merge sort version which is stableand doesn't modify the source array, though the merge requires extra memory.

另一个不简单的解决方案。这是一个稳定的合并排序版本，不会修改源数组，尽管合并需要额外的内存。

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

回答by bobfoster

The best solution would be along the lines of C's qsort, which allows you to specify functions for compare and swap, so qsort needn't be aware of the type or organization of the data being sorted. Here is one you can try. Since Java doesn't have functions, use the Array inner class to wrap the array or collection to be sorted. Then wrap that in an IndexArray and sort. The result of getIndex() on the IndexArray will be an array of indices as described in the JavaDoc.

最好的解决方案是沿用 C 的 qsort，它允许您指定比较和交换的函数，因此 qsort 不需要知道被排序的数据的类型或组织。这是您可以尝试的一种。由于 Java 没有函数，所以使用 Array 内部类来包装要排序的数组或集合。然后将其包装在一个 IndexArray 中并进行排序。IndexArray 上的 getIndex() 结果将是 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();
    }

}

回答by Gaurav

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

    }