问题：考虑以下 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)? May there be a solution that does not need to allocate a new object for each element?
更新：
感谢您的回复。不幸的是，到目前为止所提出的解决方案都不像我所希望的简单而有效的解决方案。因此，我在 JDK 反馈论坛中开了一个帖子，建议添加一个新的类库函数来解决这个问题。让我们看看 Sun/Oracle 对这个问题的看法。
http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0
创建索引器数组的简单解决方案：对比较数据值的索引器进行排序：
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]);
}
});
创建
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();
索引将按它们指向的浮点数排序，原始数组不变。如果确实有必要，请将
Collection<Integer>int[]编辑： 正如评论中所述，如果浮点数组中存在重复值，则此方法不起作用。这可以通过将
Map<Float, Integer>Map<Float, List<Integer>>我会定制快速排序算法以同时对多个数组执行交换操作：索引数组和值数组。例如（基于这个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 8功能（无需额外的库），简洁的实现方式。
int[] a = {1,6,2,7,8}
int[] sortedIndices = IntStream.range(0, a.length)
.boxed().sorted((i, j) -> Integer.compareTo(a[i], a[j]))
.mapToInt(ele -> ele).toArray();
使用 函数式 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();
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);
}
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();
}
}
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;
}
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;
}
}
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)];
}
//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;
}
public class SortedArray<T extends Comparable<T>> {
private final T[] tArray;
private final ArrayList<Entry> entries;
public class Entry implements Comparable<Entry> {
public int index;
public Entry(int index) {
super();
this.index = index;
}
@Override
public int compareTo(Entry o) {
return tArray[index].compareTo(tArray[o.index]);
}
}
public SortedArray(T[] array) {
tArray = array;
entries = new ArrayList<Entry>(array.length);
for (int i = 0; i < array.length; i++) {
entries.add(new Entry(i));
}
Collections.sort(entries);
}
public T getSorted(int i) {
return tArray[entries.get(i).index];
}
public T get(int i) {
return tArray[i];
}
}
public static int[] insertionSort(float[] arr){
int[] indices = new int[arr.length];
indices[0] = 0;
for(int i=1;i<arr.length;i++){
int j=i;
for(;j>=1 && arr[j]<arr[j-1];j--){
float temp = arr[j];
arr[j] = arr[j-1];
indices[j]=indices[j-1];
arr[j-1] = temp;
}
indices[j]=i;
}
return indices;//indices of sorted elements
}
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;
}
}