java 自定义排序java数组

custom sorting a java array

提问by epeleg

I have an [] that has some numbers (distances from some point).
I want to create an array of indexes into the first array where the indexes are sorted by the distance.

我有一个 [] 有一些数字（距某个点的距离）。
我想在第一个数组中创建一个索引数组，其中索引按距离排序。

e.g.

例如

suppose double[] dist=new double[5] {3.2, 1.4, 7.3, 2.2, 9.1};
then I want to get an array like this:

假设double[] dist=new double[5] {3.2, 1.4, 7.3, 2.2, 9.1};
然后我想得到一个这样的数组：

int[] sortedIndexes=new int[5] {1, 3, 0, 2, 4};

int[] sortedIndexes=new int[5] {1, 3, 0, 2, 4};

so if I want the second nearest distance I can check dist[sortedIndexes[1]].
I don't want to sort the original array, just the array of indexes based on the distances.

所以如果我想要第二个最近的距离，我可以检查 dist[sortedIndexes[1]]。
我不想对原始数组进行排序，只想对基于距离的索引数组进行排序。

UPDATE 1: The Code I was trying looks like this:

更新 1：我尝试的代码如下所示：

Collections.sort(sortedIDXs, new Comparator<Integer>() {
    public int compare(int idx1, int idx2) {
        return Double.compare(distances[idx1], distances[idx2]);
    }
});

But I am getting several errors with it with the most "problematic" one being: "Cannot refer to a non-final variable distances inside an inner class defined in a different method"

但是我遇到了几个错误，其中最“有问题”的是：“无法引用以不同方法定义的内部类中的非最终变量距离”

Thanks

谢谢

回答by Don Roby

You're on the right track, but

你在正确的轨道上，但是

• You're better off with an Integerarray than an intarray if you're using a generic Comparator<Integer>.
• You have to use Arrays.sortinstead Collections.sortfor sorting an array.

• You have to make the distances variable final if it's referenced in an anonymous inner class.

  final double[] distances=new double[]{3.2, 1.4, 7.3, 2.2, 9.1};
  Integer[] sortedIDXs  = new Integer[]{0,1,2,3,4};
  Arrays.sort(sortedIDXs, new Comparator<Integer>() {
      public int compare(Integer idx1, Integer idx2) {
          return Double.compare(distances[idx1], distances[idx2]);
      }
  });
  

• 你有更好Integer阵列比int，如果您使用的是通用的阵列Comparator<Integer>。
• 你必须使用Arrays.sort，而不是Collections.sort用于排序的数组。

• 如果在匿名内部类中引用了 distances 变量，则必须将它设为 final。

  final double[] distances=new double[]{3.2, 1.4, 7.3, 2.2, 9.1};
  Integer[] sortedIDXs  = new Integer[]{0,1,2,3,4};
  Arrays.sort(sortedIDXs, new Comparator<Integer>() {
      public int compare(Integer idx1, Integer idx2) {
          return Double.compare(distances[idx1], distances[idx2]);
      }
  });
  

回答by Justin

Works well if you want the indicies as a primative int array then you will have to create your own binary sorter which shouldn't be to difficult.

如果您希望索引作为原始 int 数组，则效果很好，那么您将不得不创建自己的二进制排序器，这应该不会太困难。

Edit: I adapted java's mergesorter to work with int's. This should save you a little time in writing your own.

编辑：我改编了 java 的 mergesorter 以与 int 一起工作。这应该可以为您节省一些时间来编写自己的。

public static void main(String[] args) {
        double[] dist = new double[] {3.2, 1.4, 7.3, 2.2, 9.1};
        int[] indices = createIndicies(dist);

        System.out.println(Arrays.toString(dist) + " " +  Arrays.toString(indices));
    }

    public static int[] createIndicies(double[] array) {
        int[] intArray = new int[array.length];
        for (int j = 0; j < array.length; j++) {
            intArray[j] = j;
        }

        int[] indicies = intArray.clone();
        mergeSort(intArray, indicies, 0, intArray.length, 0, new IndiciesSorter(array));

        return indicies;
    }

    public static class IndiciesSorter implements Comparator<Integer> {

        double[] array;

        public IndiciesSorter(double[] array) {
            this.array = array;
        }

        @Override
        public int compare(Integer o1, Integer o2) {
            return Double.compare(array[o1], array[o2]);
        }
    }

    private static void mergeSort(int[] src, int[] dest, int low,
            int high, int off, Comparator c) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < 7) {
            for (int i = low; i < high; i++)
                for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid - 1], src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    private static void swap(int[] x, int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

回答by creativeby

I did try it now and it works! :)

我现在确实尝试过，并且有效！:)

double[] dist= {3.2, 1.4, 7.3, 2.2, 9.1}; // your array
int[] sortedIndexes= new int[dist.length]; // your array

double[] temp = dist.clone(); // clone the array
Arrays.sort(temp); // Use native array sort function

for(int i = 0; i<temp.length; i++) { // iterate through sorted array
    for(int j = 0; j<dist.length; j++) { // iterate through original array
        if (dist[j] == temp[i]) { // if sorted value == unsorted value
            sortedIndexes[i] = j; // save position of match into your sortedIndex array
        }
    }
}

回答by John John Pichler

You should customize your own Comparator and use java API.

您应该自定义自己的 Comparator 并使用 java API。

http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[],%20int,%20int)

http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[],%20int,%20int)

http://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

http://docs.oracle.com/javase/tutorial/collections/interfaces/order.html