如何在Java中查找排序排序

Question

我想對數組進行排序並按排序順序查找每個元素的索引。 因此，舉例來說，如果我陣列上運行此：

[3,2,4] 

我會得到：

[1,0,2] 

有沒有一種簡單的方法在Java中做到這一點？

Answer 1

讓我們假設你的元素存儲在一個數組中。

final int[] arr = // elements you want 
List<Integer> indices = new ArrayList<Integer>(arr.length); 
for (int i = 0; i < arr.length; i++) { 
    indices.add(i); 
} 
Comparator<Integer> comparator = new Comparator<Integer>() { 
    public int compare(Integer i, Integer j) { 
    return Integer.compare(arr[i], arr[j]); 
    } 
} 
Collections.sort(indices, comparator); 

現在indices包含按排序順序排列的數組索引。您可以用簡單的for循環將其轉換回int[]。

Answer 2

import java.util.*; 
public class Testing{ 
    public static void main(String[] args){ 
     int[] arr = {3, 2, 4, 6, 5}; 
     TreeMap map = new TreeMap(); 
     for(int i = 0; i < arr.length; i++){ 
      map.put(arr[i], i); 
     } 
     System.out.println(Arrays.toString(map.values().toArray())); 
    } 
} 

Answer 3

實現此目的的一種方法是將起始索引對的列表作爲該對的第二部分。按照字典順序對列表進行排序，然後從排序的數組中讀取起始位置。

啓動陣列：

[3,2,4] 

添加對與起始索引：

[(3,0), (2,1), (4,2)] 

排序它lexicographically

[(2,1), (3,0), (4,2)] 

然後讀出每對中的第二部分

[1,0,2] 

Answer 4

import java.io.*; 

public class Sample { 
    public static void main(String[] args) { 
     int[] data = {0, 3, 2, 4, 6, 5, 10};//case:range 0 - 10 
     int i, rangeHigh = 10; 
     int [] rank = new int[rangeHigh + 1]; 
     //counting sort 
     for(i=0; i< data.length ;++i) ++rank[data[i]]; 
     for(i=1; i< rank.length;++i) rank[i] += rank[i-1]; 
     for(i=0;i<data.length;++i) 
      System.out.print((rank[data[i]]-1) + " ");//0 2 1 3 5 4 6 
    } 
} 

Answer 5

作爲一個更新，在Java 8中使用流式API相對比較容易。

public static int[] sortedPermutation(final int[] items) { 
    return IntStream.range(0, items.length) 
    .mapToObj(value -> Integer.valueOf(value)) 
    .sorted((i1, i2) -> Integer.compare(items[i1], items[i2])) 
    .mapToInt(value -> value.intValue()) 
    .toArray(); 
} 

它有些不幸需要用於索引的裝箱和拆箱步驟，因爲不存在.sorted(IntComparator)方法上IntStream，或甚至IntComparator功能接口對這一問題。

推廣到Comparable的List對象是非常簡單的：

public static <K extends Comparable <? super K>> int[] sortedPermutation(final List<K> items) { 
    return IntStream.range(0, items.size()) 
    .mapToObj(value -> Integer.valueOf(value)) 
    .sorted((i1, i2) -> items.get(i1).compareTo(items.get(i2))) 
    .mapToInt(value -> value.intValue()) 
    .toArray(); 
}