如何按照索引对数组进行排序？（SortIndex）

Question

我有一个包含数值的long[]数组。我需要的是一个已排序的数组，其中包含第一个数组的索引。

例如：

输入：

long[ ] values = {1 , 3 , 2 , 5 , 4};

输出：

long[ ] SortIndex = {0 , 2 , 1 , 4 , 3}

这意味着：

values[0] < values[2] < values[1] < values[4] < values[3] 

按照 SortIndex 的升序或降序并不重要。

- SAbbasizadeh

---

欢迎来到Stack Overflow！当您提问时，在右侧有一个名为“如何格式化”的框。值得一读的是通过文本区域上方的**[?]**按钮可以访问的各种内容，以及这个编辑提示页面：http://stackoverflow.com/editing-help 这次我已经帮您整理了问题。 - T.J. Crowder

非常感谢您的编辑。不，不能保证这些值是唯一的。 - SAbbasizadeh

Answer 1

long[] values = {1 , 3 , 2 , 5 , 4};
Map<Long, Integer> indices = new HashMap<Long, Integer>();
for (int index = 0; index < values.length; index++) {
    indices.put(values[index], index);
}

long[] copy = Arrays.copyOf(values, values.length);
Arrays.sort(copy);
for (int index = 0; index < copy.length; index++) {
    copy[index] = indices.get(copy[index]);
}

你的索引列表将会在copy中。

此处有一个工作示例：http://ideone.com/A9Imz

- aroth

---

当您的值是唯一的时，这是正确的。我不认为他提到过任何这样的限制。 - prap19

相反，一个更简单的实现方法是编写自己的排序算法，在值交换步骤中同时交换“sortedIndex”。http://www.roseindia.net/java/beginners/arrayexamples/mergeSort.shtml 如果需要，我可以编写代码来说明如何实现。 - prap19

@prap19 - 我不会称那为“更简单”的解决方案。即使使用一个微不足道/低效的排序算法，它肯定需要比上面显示的代码更多的代码。但是，如果解决方案需要正确处理重复值，那么这确实是必要的方法。 - aroth

是的，“更简单”是指在您的情况下不使用额外的数据结构，例如哈希表？我们需要吗？ - prap19

Answer 2

您可以通过向TreeMap添加Long对来实现此操作，其中键是values[index]，值是index。

遍历映射的iterator将产生排序索引值。

更新

看到没有被接受的答案，这里是根据对此答案的评论进行跟进后得出的代码。

    long[] values = { 1 , 3 , 2 , 5 , 4 };
    int[]  output = new int[values.length];

    Map<Long, Integer> map = new TreeMap<Long, Integer>();

    for (int n = 0; n < values.length; n++) {
        map.put(values[n] * values.length + n, n);
    }

    int n = 0;

    for (Integer index: map.values()) {
        output[n++] = index;
    }

    System.out.println(Arrays.toString(output));

输出：

[0, 2, 1, 4, 3]

当输入中包含重复内容时，该解决方案同样有效：

long[] values = { 8, 5, 3, 2, 1, 1 };

输出：

[4, 5, 3, 2, 1, 0]

如果可以将 sortOrder 数组作为 Integer 数组接收，第二个循环可以替换为：

Integer[] output = map.values().toArray(new Integer[values.length]);

- rsp

---

@prap19，TreeMap将按自然顺序对其键进行排序，迭代映射（map.entrySet().iterator()）将按排序后的值作为键，并将它们的原始索引作为值。 - rsp

SortIndex[] 是一个索引数组，它与 values[] 数组中数字的自然索引不同。在排序之后，您仍然能够将值映射到其指向的索引吗？ - prap19

当然，如果映射更改键值对，它就不会是一个映射了 :-) 在迭代映射时，您只需将其值存储在“sortIndex”数组中，这就是您的输出。 - rsp

@AKJ，如果值不唯一，您可以通过使用values[index] * values.length + index作为键来使它们的映射键唯一 :-) - rsp

Answer 3

一个简单的想法是在每次迭代中找到最小值的索引，然后将一个大值放入该索引。即使存在重复值，这也可以起作用。 例如：

long[] values = { 1, 3, 2, 5, 4 };

long[] indices = new long[values.length];
for (int i = 0; i < values.length; i++) {
    long min = Long.MAX_VALUE;
    int minIndex = 0;
    for (int j = 0; j < values.length; j++) {
        if (min > values[j]) {
            minIndex = j;
            min = values[j];
        }
    }
    values[minIndex] = Long.MAX_VALUE;
    indices[i] = minIndex;
}

System.out.println(Arrays.toString(indices));

- Ashwinee K Jha

Answer 4

我通过使用Java的Comparator接口找到了另一种优雅的解决方案。即使值不唯一，它也可以正常工作：

final Long[] values = { 1, 3, 2, 5, 4, 2};
Integer[] indices = new Integer[values.length];
for (int i = 0; i < indices.length; i++) {
    indices[i] = i;
}
Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer arg0, Integer arg1) {
        return values[arg0].compareTo(values[arg1]);
    }
};
Arrays.sort(indices, comparator);
System.out.println(Arrays.toString(indices));

输出：

[0, 2, 5, 1, 4, 3]

• 您可以通过更改 compare（） 方法中的比较顺序，将输出顺序从升序更改为降序：

  public int compare(Integer arg0, Integer arg1) {
      return values[arg1].compareTo(values[arg0]);
  }
  

• 您还可以将 Long[] 更改为任何其他可比较数据类型。

- SAbbasizadeh