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

Question

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

42

问题：考虑以下floats[]数组：

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

- edgar.holleis

即使这个功能被放入JDK中，我真的很怀疑会发生这种情况，它最终会成为Arrays类（或类似的类）上的静态实用方法，并且最终会被实现得非常类似于下面的内容。那么你为什么不能自己编写这个函数呢？ - Jherico

自定义比较器作为解决方案有什么问题吗？我可能误解了您心中的方法。 - jerryjvl

也许我没有找到足够的信息，但据我所知，没有办法在不对每个元素进行装箱的情况下使用Comparator。对于一个包含n个浮点数的数组，这意味着垃圾收集器需要2nlog(n)个Floats。当n=10000时，这意味着有80000个垃圾。我更喜欢在Arrays类中使用静态实用程序方法。如果我不关心垃圾，我本来可以一开始就使用TreeMap或其他东西。 - edgar.holleis

这非常有用，我希望你能在Java中实现它。在R中，您只需使用rank()函数即可。 - twolfe18

如果您的数字少于5000个，只需使用冒泡排序。它易于阅读，简短且足够快。 - Thomas Ahle

可以使用Java 8的<5行代码完成，https://dev59.com/MnNA5IYBdhLWcg3wdtpd#35701049 - Pratap Koritala

15个回答

23

创建一个将值映射到索引的 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将按照它们所指向的浮点数进行排序，原始数组不受影响。如果确实需要，将Collection<Integer>转换为int[]留作练习。

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

- Jherico

我正在精确地进行映射。 - Tetsujin no Oni

使用了不幸大量的自动装箱，但起到了作用。+1 - Michael Myers

9

这种方法的缺陷在于它不能处理重复的浮点数值。 - Mark

18

使用Java 8功能（无需额外库），简洁实现它的方法。

int[] a = {1,6,2,7,8}
int[] sortedIndices = IntStream.range(0, a.length)
                .boxed().sorted((i, j) -> Integer.compareTo(a[i], b[i]))
                .mapToInt(ele -> ele).toArray();

- Pratap Koritala

很好。如果我有一个元素列表或数组，其中不允许使用 a[i] - a[j] 怎么办？ - törzsmókus

2

你可以使用compareTo https://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html#compareTo(T)。 - Pratap Koritala

1

修改了Integer.compareTo的答案，因为a[i] - b[i]可能会导致整数溢出。 - Pratap Koritala

b[i] 应该是 a[j]，但这个修改太小了，不足以被视为编辑。 - squaregoldfish

18

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

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

4

尽管行数超出了所需的小于5行的要求，但这是迄今为止唯一提供并保持合理性能特征的解决方案。很抱歉，朋友们 :-( - edgar.holleis

3

这很悲哀。我有同样的问题，而这是对于大数据集唯一可接受的解决方案。 - ansgri

4

但是这个解决方案修改了数据数组。通常排序索引的目的是避免修改数据顺序。要使其只读，不要在exch()函数中交换数据，并将每个a[x]替换为a[index[x]]。 - xan

终于有人懂了！谢谢！ - stolsvik

7

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

- Apocalisp

5

请不要误解我的意思，但是-哇！这段代码完全无法读懂！很抱歉-我忍不住要这么说 :-) 但是它确实符合小于5行的代码要求-包括import语句-非常令人印象深刻！ - Kevin Day

5

什么意思是"Unreadable how?"。让我们读一下它。将你的数组带到一个流中，将每个元素与其索引配对（zip），按照配对顺序（先按双重排序，然后按整数排序）进行快速排序，获取每个配对的后半部分，然后将所有内容带到一个数组中。很容易！ - Apocalisp

只有当你刚接触函数式编程时，这才是难以理解的。在函数式语言中，这种情况非常普遍。在Java 8中是否可以不使用第三方库来完成这个任务？ - SigmaX

3

更一般的情况是允许重复值的Jherico答案，代码如下：Jherico's answer。

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

- Mark Elliot

我认为应该在 ind.add(i); 之后放置 map.put(array[i], ind);。 - lizzie

@lizzie，它可以直接工作，因为ind保存了列表的位置，并且被ind.add更新的对象将与映射中的对象相同。 - Mark Elliot

2

最好的解决方案类似于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();
    }

}

- bobfoster

2

public static int[] indexSort(final double[] v, boolean keepUnsorted) {
    final Integer[] II = new Integer[v.length];
    for (int i = 0; i < v.length; i++) II[i] = i;
    Arrays.sort(II, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Double.compare(v[o1],v[o2]);
        }
    });
    int[] ii = new int[v.length];
    for (int i = 0; i < v.length; i++) ii[i] = II[i];
    if (!keepUnsorted) {
        double[] clon = v.clone();
        for (int i = 0; i < v.length; i++) v[i] = clon[II[i]];
    }
    return ii;
}

- user3608841

如果您在此代码中添加一个简短的解释，那将更好。 - vefthym

不错！我喜欢这个！ - Ofek Ron

0

我想使用这个，因为它非常快。但是如果你用它来处理整数，你可以将它改成浮点数。

private static void mergeSort(int[]array,int[] indexes,int start,int end){
    if(start>=end)return;
    int middle = (end-start)/2+start;
    mergeSort(array,indexes,start,middle);
    mergeSort(array,indexes,middle+1,end);
    merge(array,indexes,start,middle,end);
}
private static void merge(int[]array,int[] indexes,int start,int middle,int end){
    int len1 = middle-start+1;
    int len2 = end - middle;
    int leftArray[] = new int[len1];
    int leftIndex[] = new int[len1];
    int rightArray[] = new int[len2];
    int rightIndex[] = new int[len2];
    for(int i=0;i<len1;++i)leftArray[i] = array[i+start];
    for(int i=0;i<len1;++i)leftIndex[i] = indexes[i+start];
    for(int i=0;i<len2;++i)rightArray[i] = array[i+middle+1];
    for(int i=0;i<len2;++i)rightIndex[i] = indexes[i+middle+1];
    //merge
    int i=0,j=0,k=start;
    while(i<len1&&j<len2){
        if(leftArray[i]<rightArray[j]){
            array[k] = leftArray[i];
            indexes[k] = leftIndex[i];
            ++i;
        }
        else{
            array[k] = rightArray[j];
            indexes[k] = rightIndex[j];
            ++j;
        }
        ++k;
    }
    while(i<len1){
        array[k] = leftArray[i];
        indexes[k] = leftIndex[i];
        ++i;++k;
    }
    while(j<len2){
        array[k] = rightArray[j];
        indexes[k] = rightIndex[j];
        ++j;++k;
    }
}

- Smart Du

0

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

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

- xan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- carloscs · Accepted Answer

创建索引器数组的简单解决方案：根据数据值排序索引器：

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