问题:考虑以下 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 的排序函数。
有没有一种简单的方法可以做到这一点(<5 LOC)? 是否有一种解决方案不需要为每个元素分配一个新对象?
更新:
感谢您的回复。 不幸的是,到目前为止所提出的方案都不像我所希望的简单而有效的解决方案。 因此,我在 JDK 反馈论坛中开了一个帖子,建议添加一个新的类库函数来解决这个问题。 让我们看看 Sun/Oracle 对这个问题的看法。
http://forums.java.net/jive/thread。 jspa?threadID=62657&tstart=0
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.
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.
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?
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.
http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0
发布评论
评论(15)
创建索引器数组的简单解决方案:对比较数据值的索引器进行排序:
Simple solution to create an indexer array: sort the indexer comparing the data values:
创建索引值的
TreeMap
索引将按它们指向的浮点数排序,原始数组保持不变。 如果确实有必要,将
Collection
转换为int[]
留作练习。编辑:
正如评论中所述,如果浮点数组中存在重复值,则此方法不起作用。 可以通过将
Map
转换为Map>
来解决此问题,尽管这会使 for 循环内部变得复杂,并且最终收藏的一代咯。Create a
TreeMap
of values to indicesindices will be the sorted by the floats they point to, the original array is untouched. Converting the
Collection<Integer>
to aint[]
is left as an exercise if it's really necessary.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 aMap<Float, List<Integer>>
though this will complicate the inside of the for loop and the generation of the final collection slightly.我将定制快速排序算法以同时对多个数组执行交换操作:索引数组和值数组。 例如(基于此quicksort):
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):
使用Java 8功能(无需额外的库),简洁的实现方式。
Using Java 8 features ( without extra library) , concise way of achieving it.
对于函数式 Java:
With Functional Java:
Jherico 允许重复值的答案是这样的:
The more general case of Jherico's answer that allows duplicate values would be this:
最好的解决方案是沿着 C 的 qsort 的思路,它允许您指定比较和交换的函数,因此 qsort 不需要知道正在排序的数据的类型或组织。 您可以尝试一下。 由于Java没有函数,因此使用Array内部类来包装要排序的数组或集合。 然后将其包装在 IndexArray 中并排序。 IndexArray 上的 getIndex() 的结果将是一个索引数组,如 JavaDoc 中所述。
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.
将输入转换为如下所示的pair类,然后使用Arrays.sort()对其进行排序。 Arrays.sort() 确保保留相等值的原始顺序,就像 Matlab 所做的那样。 然后,您需要将排序结果转换回单独的数组。
}
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.
}
另一个非简单的解决方案。 这是一个合并排序版本,它稳定并且不会修改源数组,尽管合并需要额外的内存。
Another non-simple solution. Here's a merge sort version which is stable and doesn't modify the source array, though the merge requires extra memory.
我会做这样的事情:
I would do something like this:
下面是一种基于插入排序的方法
Below is a method based on Insertion Sort
我想使用它,因为它非常快。但是我将它用于 int,你可以将其更改为 float。
I'd like to use this because it is very fast.But I use it for int,you can change it to float.
我想最简单的方法是在创建数组时对其进行索引。 您需要键值对。 如果索引是一个单独的结构,那么我看不出在没有其他对象的情况下如何做到这一点(尽管有兴趣看到它)
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)