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

Question

Это вопрос интервью.

Есть несколько случайных чисел (скажем, в массиве целых чисел).

1. Как мы можем сначала отсортировать все четные числа в порядке возрастания, а затем отсортировать все нечетные числа в порядке убывания.
2. Какая коллекция подходит лучше всего.

Ввод чисел:

12 67 1 34 9 78 6 31

Вывод сохранен в коллекции:

6 12 34 78 67 31 9 1 

Answer 1

Подойдет любая коллекция, которая поддерживает сортировку с помощью пользовательского компаратора - даже массив. Реализуйте свой собственный компаратор следующим образом:

public int compare(int x, int y) {
    if (x&1 == y&1) {
        // Both numbers are odd or both numbers are even
        if (x&1 == 0) {
            // Both numbers are even: compare as usual
            return Integer.compare(x, y);
        } else {
            // Both numbers are odd: compare in reverse
            return Integer.compare(y, x);
        }
    }
    // One is odd, the other one is even
    if (x&1 == 0) {
        return -1;
    }
    return 1;
}

Answer 2

Вы можете сделать следующее:

public ArrayList<Integer> sort(Integer[] input) {
        int length = input.length;
        ArrayList<Integer> oddNumber = new ArrayList<Integer>(0);
        ArrayList<Integer> evenNumber = new ArrayList<Integer>(0);
        for (int i = 0; i < length; i++) {
            Integer val = input[i];
            if(isEven(val)){
                evenNumber.add(val);
            } else {
                oddNumber.add(val);
            }
        }
        Collections.sort(evenNumber);
        Collections.sort(oddNumber, Collections.reverseOrder());

        evenNumber.addAll(oddNumber);

        return evenNumber;
    }

    public boolean isEven(Integer x) {
        return x % 2 == 0;
    }

РЕДАКТИРОВАТЬ

Я реализовал компаратор на основе алгоритма Джеспера.

public ArrayList<Integer> sort(Integer[] input) {
        ArrayList<Integer> output = new ArrayList<Integer>(0);
        output.addAll(Arrays.asList(input));

        Collections.sort(output, new EvenOddComparator());

        return output;
    }

    public class EvenOddComparator implements Comparator<Integer>
    {
        final int BEFORE = -1;
        final int EQUAL = 0;
        final int AFTER = 1;

        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 % 2 == 0 && o2 % 2 != 0) {
                return BEFORE;
            } else if (o1 % 2 != 0 && o2 % 2 == 0) {
                return AFTER;
            } else if (o1 % 2 == 0 && o2 % 2 == 0) {
                return o1.compareTo(o2);
            } else if (o1 % 2 != 0 && o2 % 2 != 0) {
                return o2.compareTo(o1);
            }
            return EQUAL;
        }

    }

Приветствия.

Answer 3

package com.java.util.collection;

import java.util.Arrays;
import java.util.Collections;

public class EvenOddSorting {

    public static void eventOddSort(int[] arr) {
        int i =0;
        int j =arr.length-1;
        while(i<j) {
            if(isEven(arr[i]) && isOdd(arr[j])) {
                i++;
                j--;
            } else if(!isEven(arr[i]) && !isOdd(arr[j])) {
                swap(i,j,arr);
            } else if(isEven(arr[i])){
                i++;
            } else{
                j--;
            }

        }   
        display(arr);
        // even number sorting
        Arrays.sort(arr,0,i);
        insertionSort(arr,i,arr.length);
        // odd number sorting
        display(arr);

    }

    /**
     * Instead of insertion sort, you can use merge or quick sort.
     * @param arr
     * @param firstIndex
     * @param lastIndex
     */
    public static void insertionSort(int[] arr, int firstIndex, int lastIndex){
        for(int i=firstIndex+1;i<lastIndex;i++){
            int key =arr[i];
            int j=i-1;
            while(j>=firstIndex  && key > arr[j]) {
                arr[j+1] = arr[j];
                arr[j] =key;
                j=j-1;
            }
            System.out.println("\nAfter "+(i+1) +"  Iteration : ");
            display(arr);
        }
    }

    public static void display(int[] arr) {
        System.out.println("\n");
        for(int val:arr){
            System.out.print(val +"  ");
        }
    }

    private static void swap(int pos1, int pos2, int[] arr) {
        int temp = arr[pos1];
        arr[pos1]= arr[pos2];
        arr[pos2]= temp;
    }

    public static boolean isOdd(int i) {
        return (i & 1) != 0;
    }
    public static boolean isEven(int i) {
        return (i & 1) == 0;
    }
    public static void main(String[] args) {
        int arr[]={12, 67, 1, 34, 9, 78, 6, 31};
        eventOddSort(arr);
    }
}

Answer 4

Вот код:

@Override
public int compare(Integer o1, Integer o2) {
    if (o1 % 2 ==0) 
    {
        if (o2 % 2 == 0)
        {
            if (o1 < o2)
                return -1;
            else
                return 1;
        }
        //if (o2 % 2 != 0)
        else
        {
            return -1;
        }
    }
    else 
    {
        if (o2 % 2 != 0)
        {
            if (o1 < o2)
                return 1;
            else
                return -1;
        }
        //if (o2 % 2 == 0)
        else
        {
            return 1;
        }
    }
}

Answer 5

Если вам не требуется реализовывать весь алгоритм сортировки самостоятельно, вы можете просто использовать Collections.sort(list, comparator), и вам нужно будет предоставить собственную реализацию Comparator<Integer>, которая сравнивает числа и возвращает результат, так что числасортируются в порядке, определенном правилами.

Компаратор должен реализовать эти правила:

1. Если первое число четное, а второе нечетное, вернуть -1(поскольку четные числа должны предшествовать нечетным числам).
2. Если первое число нечетное, а второе четное, верните 1 (поскольку четные числа должны предшествовать нечетным числам).
3. Если оба числачетные: сравнить оба числа, вернуть -1, если первое <секунда, 0, если равно, 1 если первое> секунда (сортирует четные числа по возрастанию).
4. Если оба числа нечетные: сравнить оба числа, вернуть 1, еслиfirst second (сортирует нечетные числа по убыванию).

Если у вас есть числа в массиве вместо List, используйтеArrays.sort(array, comparator).

Answer 6

в Java: - Лучший подход, минимальная сложность

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class EvenOddSorting {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i, size;
        ArrayList<Integer> listEven = new ArrayList<Integer>();
        ArrayList<Integer> listOdd = new ArrayList<Integer>();
        ArrayList<Integer> finalList = new ArrayList<Integer>();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter Array Size : ");
        size = sc.nextInt();
        int A[] = new int[size];
        for (i = 0; i < size; i++) {
            A[i] = sc.nextInt();
        }
        for (i = 0; i < size; i++){
            if (A[i] % 2 == 0){
                listEven.add(A[i]);
            }
            else if (A[i] % 2 != 0) {
                listOdd.add(A[i]);
            }
        }
        Collections.sort(listEven);
        Collections.sort(listOdd);
        Collections.reverse(listOdd);
        finalList.addAll(listOdd);
        finalList.addAll(listEven);
        System.out.println("Result is : "+finalList);
    }
}

Вывод: -

Введите размер массива: 10

1 2 3 4 5 6 7 8 910 Результат: [9, 7, 5, 3, 1, 2, 4, 6, 8, 10]

Answer 7

Я только что написал быстрый пример, как показано ниже:

public class CustomSorting {
    public static void main(String[] args) {
        Integer[] intArray = new Integer[] {12, 67, 1, 34, 9, 78, 6, 31};
        Arrays.sort(intArray, new Comparator() {
            @Override
            public int compare(Object obj1, Object obj2) {
                Integer int1 = (Integer) obj1;
                Integer int2 = (Integer) obj2;

                int mod1 = Math.abs(int1%2);
                int mod2 = Math.abs(int2%2);

                return ((mod1 == mod2) ? ((mod1 == 0) ? int1.compareTo(int2) : int2.compareTo(int1)) : ((mod1 < mod2) ? -1 : 1));
            }
        });
    }
}

Выход :

[6, 12, 34, 78, 67, 31, 9, 1]

Answer 8

Я бы нормализовал все числа, а затем отсортировал их.

public static void main(String[] args) {
    int[] values = {Integer.MIN_VALUE, 0, Integer.MAX_VALUE - 1, Integer.MIN_VALUE + 1, -1, 1, Integer.MAX_VALUE};
    for (int i = 0; i < values.length; i++) {
        int value = encode(values[i]);
        assert decode(value) == values[i];
        values[i] = value;
    }
    Arrays.sort(values);
    for (int i = 0; i < values.length; i++)
        // give back the original value.
        values[i] = decode(values[i]);
    System.out.println(Arrays.toString(values));
}

private static int decode(int value) {
    return value >= 0
            ? Integer.MAX_VALUE - (value << 1)
            : Integer.MIN_VALUE + (value << 1);
}

private static int encode(int value) {
    return (value & 1) == 0
            ? (value >> 1) + Integer.MIN_VALUE / 2
            : Integer.MAX_VALUE / 2 - (value >> 1);
}

печать

[-2147483648, 0, 2147483646, 2147483647, 1, -1, -2147483647]

Здесь происходит дополнительное смещение, поэтому очень большие числа не искажаются. (именно поэтому число делится на два)

Answer 9

Как это:

var list = new List<int>{1,5,2,6,3,9,10,11,12};

var sorted = list.Where (l => l%2 ==0).OrderBy (l=>l).Union(list.Where (l => l%2 != 0).OrderByDescending (l=>l));

Answer 10

Ad1. Нам нужно создать Comparator<Tnteger>, который работает с этими правилами.

1. Если мы сравним четное число с нечетным, то четное всегда будет больше.
2. Если мы сравним два нечетных числа, результат будет таким, каким мы хотели бы его отсортировать.
3. Если мы сравним два четных числа, результат будет таким, как мы хотели бы отсортировать.

Ad2. Я не понимаю.