Java数组sorting：快速获取数组索引的sorting列表
问题：Consder下面的花车[]：
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
当然，也可以使用自定义比较器，一组有序的对象，或者简单地对数组进行sorting，然后search原始数组中的索引（颤抖）。
我实际上在寻找的是Matlab的sorting函数的第二个返回参数的等价物。
有没有一个简单的方法来做到这一点（<5 LOC）？ 可能有一个解决scheme，不需要为每个元素分配一个新的对象？
更新：
感谢您的回应。 不幸的是，到目前为止所提出的一切都不是我期望的简单而有效的解决scheme。 因此，我在JDK反馈论坛中开辟了一个线程，提出增加一个新的类库函数来解决这个问题。 让我们看看Sun / Oracle对这个问题的看法。
http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0
我将定制quicksortalgorithm来同时对多个数组执行交换操作：索引数组和值数组。 例如（基于这个快速sorting ）：
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; }
创build索引器数组的简单方法：对比较数据值的索引器进行sorting：
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]); } });
创build索引值的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();
索引将按照它们指向的浮点数sorting，原始数组不变。 如果真的有必要，将Collection<Integer>转换为int[]将作为练习。
编辑：如注释中所述，如果浮点数组中存在重复的值，则此方法不起作用。 这可以通过将Map<Float, Integer> Map<Float, List<Integer>>到Map<Float, List<Integer>>尽pipe这会使for循环的内部和最终集合的生成稍微复杂化。
使用Java 8的function（无需额外的库），简洁的方式来实现它。
int[] a = {1,6,2,7,8} int[] sortedIndices = IntStream.range(0, a.length) .boxed().sorted((i, j) -> a[i] - a[j]) .mapToInt(ele -> ele).toArray();
使用function性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); }
最好的解决scheme是沿着C的qsort行，它允许你指定比较和交换的函数，所以qsort不需要知道被sorting数据的types或组织。 这里是你可以尝试的一个。 由于Java没有函数，所以使用Array内部类来包装要sorting的数组或集合。 然后将其包装在IndexArray中并进行sorting。 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(); } }
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; }
将input转换为类对，如下所示，然后使用Arrays.sort（）对其进行sorting。 Arrays.sort（）确保原始顺序像Matlab一样被保存为相同的值。 然后您需要将sorting的结果转换回单独的数组。
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; }
}
另一个非简单的解决scheme。 这是一个合并sorting版本，它是稳定的 ，不会修改源数组，尽pipe合并需要额外的内存。
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]; } }
下面是一个基于Insertion Sort的方法
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 }
我想用这个，因为它非常快。但是我用它来处理int，你可以把它改成float。
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; } }
我想最简单的方法是创build数组索引。 你需要键值对。 如果索引是一个单独的结构，那么我不能看到你怎么可以做到这一点没有其他对象（有兴趣看到它虽然）
