Задана последовательность
целых чисел. Отсортируйте заданную последовательность так, чтобы сначала были
расположены нечетные числа в возрастающем порядке, а потом четные числа в
убывающем порядке.
Вход.
Первая строка содержит количество чисел n
(1 ≤ n ≤ 1000). Вторая
строка содержит n чисел, не
превосходящих по модулю 2 * 109.
Выход.
В одной строке выведите последовательность чисел, упорядоченную согласно
условию задачи.
|
Пример входа |
Пример выхода |
|
7 9 2 3 -6 -5 4 7 |
-5 3 7 9 4 2 -6 |
сортировка
Отсорируем
числа согласно следующего компаратора f(int
a, int b):
·
если a и b
имеют разную четность, то четное число должно стоять после нечетного;
·
если a и b
четные, то сортировать следует по убыванию;
·
если a и b
нечетные, то сортировать следует по возрастанию;
Следует
учесть, что входные числа могут быть как положительные так и отрицательные.
Реализация алгоритма
Функция abs вычисляет
модуль числа.
int abs(int n)
{
return (n > 0) ? n
: -n;
}
Объявим компаратор f.
int f(int a, int b)
{
Если a и b имеют
разную четность, то четное число должно стоять после нечетного.
if (abs(a % 2) !=
abs(b % 2)) return abs(a % 2) > abs(b % 2);
Если a и b четные, то
сортировать следует по убыванию.
if (a % 2 == 0) return a > b;
Если a и b нечетные,
то сортировать следует по возрастанию.
if (abs(a % 2) ==
1) return a < b;
}
Основная часть программы. Читаем входную
последовательность чисел.
scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &v[i]);
Сортируем массив.
sort(v.begin(), v.end(), f);
Выводим упорядоченную последовательность чисел.
for (i = 0; i < n; i++)
printf("%d
", v[i]);
printf("\n");
Реализация алгоритма – Heap Sort
#include <stdio.h>
#define MAX 1001
int i, n;
int m[MAX];
int abs(int n)
{
return (n > 0) ? n : -n;
}
int f(int a, int b)
{
if (abs(a % 2) !=
abs(b % 2)) return abs(a % 2) > abs(b % 2);
if (a % 2 == 0) return a > b;
if (abs(a % 2) ==
1) return a < b;
}
int left(int i)
{
return 2 * i;
}
int right(int i)
{
return 2 * i + 1;
}
void swap(int &i, int &j)
{
int temp = i; i = j; j = temp;
}
// max - heap
void heapify(int a[], int i, int n, int f(int a, int b))
{
int largest = 0;
int l = left(i);
int r = right(i);
if (l <= n
&& f(a[i], a[l])) largest = l;
else largest = i;
if (r <= n
&& f(a[largest], a[r])) largest = r;
if (largest != i)
{
swap(a[i], a[largest]);
heapify(a, largest, n, f);
}
}
void BuildHeap(int a[], int n, int f(int a, int b))
{
for (int i = n / 2; i
> 0; i--)
heapify(a, i, n, f);
}
void HeapSort(int a[], int n, int f(int a, int b))
{
BuildHeap(a, n, f);
for (int i = n; i >=
2; i--)
{
swap(a[1], a[i]);
heapify(a, 1, i - 1, f);
}
}
int main(void)
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &m[i]);
HeapSort(m, n, f);
for (i = 1; i <= n; i++)
printf("%d ", m[i]);
printf("\n");
return 0;
}
Java реализация
import java.util.*;
class Main
{
public static class MyFun implements Comparator<Integer>
{
public int compare(Integer a, Integer b)
{
if (Math.abs(a % 2) != Math.abs(b % 2))
return Math.abs(b % 2) - Math.abs(a % 2);
if (a % 2 == 0) return b - a;
return a - b;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Vector<Integer> m = new Vector<Integer>();
for (int i = 0; i < n; i++)
{
int val = con.nextInt();
m.add(new Integer(val));
}
Collections.sort(m, new MyFun());
for (int i = 0; i < n; i++)
System.out.print(m.get(i) + " ");
System.out.println();
con.close();
}
}
Python реализация
from functools import cmp_to_key
def compare(a, b):
if abs(a % 2) != abs(b % 2): return abs(b % 2) - abs(a % 2)
if a % 2 == 0: return b - a;
return a - b;
n = int(input())
lst = map(int, input().split())
res = sorted(lst, key = cmp_to_key(compare))
print(*res)