Как отсортировать массив целых, используя пользовательский компаратор?

Question

Мне нужно отсортировать массив целых с использованием пользовательского компаратора, но библиотека Java не предоставляет функцию сортировки для целых с компараторами (компараторы могут использоваться только с объектами).Есть ли простой способ сделать это?

Answer 1

Если вы не можете изменить тип входного массива, будет работать следующее:

final int[] data = new int[] { 5, 4, 2, 1, 3 };
final Integer[] sorted = ArrayUtils.toObject(data);
Arrays.sort(sorted, new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        // Intentional: Reverse order for this demo
        return o2.compareTo(o1);
    }
});
System.arraycopy(ArrayUtils.toPrimitive(sorted), 0, data, 0, sorted.length);

При этом используется ArrayUtils из проекта commons-lang для простого преобразования между int[] и Integer[], создается копия массива, выполняется сортировка, а затем копируется отсортированные данные в оригинал.

Answer 2

Как насчет использования потоков (Java 8)?

int[] ia = {99, 11, 7, 21, 4, 2};
ia = Arrays.stream(ia).
    boxed().
    sorted((a, b) -> b.compareTo(a)). // sort descending
    mapToInt(i -> i).
    toArray();

Или на месте:

int[] ia = {99, 11, 7, 21, 4, 2};
System.arraycopy(
        Arrays.stream(ia).
            boxed().
            sorted((a, b) -> b.compareTo(a)). // sort descending
            mapToInt(i -> i).
            toArray(),
        0,
        ia,
        0,
        ia.length
    );

Answer 3

Если вы не хотите копировать массив (скажем, он очень большой), вы можете создать оболочку List<Integer>, которую можно использовать для сортировки:

final int[] elements = {1, 2, 3, 4};
List<Integer> wrapper = new AbstractList<Integer>() {

        @Override
        public Integer get(int index) {
            return elements[index];
        }

        @Override
        public int size() {
            return elements.length;
        }

        @Override
        public Integer set(int index, Integer element) {
            int v = elements[index];
            elements[index] = element;
            return v;
        }

    };

И теперь вы можете выполнить сортировку в этом списке Оберток, используя собственный компаратор.

Answer 4

Путем преобразования массива int в целочисленный, а затем с помощью public static <T> void Arrays.sort(T[] a, Comparator<? super T> c) (первый шаг необходим только потому, что, боюсь, автобокс может работать с ботами)

Answer 5

Вы можете использовать IntArrays.quickSort(array, comparator) из библиотеки fastutil.

Answer 6

Я старался максимально использовать компаратор с самим примитивным типом. Наконец я пришел к выводу, что нет способа обмануть компаратор. Это моя реализация.

public class ArrSortComptr {
    public static void main(String[] args) {

         int[] array = { 3, 2, 1, 5, 8, 6 };
         int[] sortedArr=SortPrimitiveInt(new intComp(),array);
         System.out.println("InPut "+ Arrays.toString(array));
         System.out.println("OutPut "+ Arrays.toString(sortedArr));

    }
 static int[] SortPrimitiveInt(Comparator<Integer> com,int ... arr)
 {
    Integer[] objInt=intToObject(arr);
    Arrays.sort(objInt,com);
    return intObjToPrimitive(objInt);

 }
 static Integer[] intToObject(int ... arr)
 {
    Integer[] a=new Integer[arr.length];
    int cnt=0;
    for(int val:arr)
      a[cnt++]=new Integer(val);
    return a;
 }
 static int[] intObjToPrimitive(Integer ... arr)
 {
     int[] a=new int[arr.length];
     int cnt=0;
     for(Integer val:arr)
         if(val!=null)
             a[cnt++]=val.intValue();
     return a;

 }

}
class intComp implements Comparator<Integer>
{

    @Override //your comparator implementation.
    public int compare(Integer o1, Integer o2) {
        // TODO Auto-generated method stub
        return o1.compareTo(o2);
    }

}

@ Роман: Я не могу сказать, что это хороший пример, но так как вы спросили, это то, что пришло мне в голову. Предположим, что в массиве вы хотите отсортировать числа только на основе их абсолютного значения.

Integer d1=Math.abs(o1);
Integer d2=Math.abs(o2);
return d1.compareTo(d2);

Другим примером может быть то, что вы хотите отсортировать только числа больше 100. Это на самом деле зависит от ситуации. Я не могу больше думать о каких-либо ситуациях. Может быть, Александр может привести больше примеров, так как говорит, что хочет использовать компаратор для массива int.

Answer 7

Вот вспомогательный метод для выполнения этой работы.

Прежде всего вам понадобится новый интерфейс Comparator, так как Comparator не поддерживает примитивы:

public interface IntComparator{
    public int compare(int a, int b);
}

(Конечно, вы могли бы сделать это с помощью автобокса / распаковки, но я не пойду туда, это ужасно)

Затем, вот вспомогательный метод для сортировки массива int с использованием этого компаратора:

public static void sort(final int[] data, final IntComparator comparator){
    for(int i = 0; i < data.length + 0; i++){
        for(int j = i; j > 0
            && comparator.compare(data[j - 1], data[j]) > 0; j--){
            final int b = j - 1;
            final int t = data[j];
            data[j] = data[b];
            data[b] = t;
        }
    }
}

А вот код клиента.Тупой компаратор, который сортирует все числа, которые состоят только из цифры «9» вперед (снова отсортированы по размеру), а затем остальные (для любого товара):

final int[] data =
    { 4343, 544, 433, 99, 44934343, 9999, 32, 999, 9, 292, 65 };
sort(data, new IntComparator(){

    @Override
    public int compare(final int a, final int b){
        final boolean onlyNinesA = this.onlyNines(a);
        final boolean onlyNinesB = this.onlyNines(b);
        if(onlyNinesA && !onlyNinesB){
            return -1;
        }
        if(onlyNinesB && !onlyNinesA){
            return 1;
        }

        return Integer.valueOf(a).compareTo(Integer.valueOf(b));
    }

    private boolean onlyNines(final int candidate){
        final String str = String.valueOf(candidate);
        boolean nines = true;
        for(int i = 0; i < str.length(); i++){
            if(!(str.charAt(i) == '9')){
                nines = false;
                break;
            }
        }
        return nines;
    }
});

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

Вывод:

[9, 99, 999, 9999, 32, 65, 292, 433, 544, 4343, 44934343]

Код сортировки был взят из Arrays.sort (int []) , и я использовал только версию, оптимизированную для крошечных массивов.Для реальной реализации вы, вероятно, захотите взглянуть на исходный код внутреннего метода sort1(int[], offset, length) в классе Arrays .