Сортировка нечетных по убыванию и даже по возрастанию

Question

Учитывая массив случайных чисел, сортируйте нечетные элементы в порядке убывания и четные числа в порядке возрастания.

Пример входных данных: (1,4,5,2,3,6,7)
Выход: (7,5,3,1,2,4,6)

Оптимизировать для временной сложности.

Answer 1

Какой язык это, C или C++ (я вижу, как теги)

В C++ можно использовать std::sort() с соответствующей функцией заказа. В C qsort() работает аналогично:

#include <iostream> 
#include <algorithm> 
bool Order(int a, int b) 
{ 
     if (a%2 != b%2) return a%2; 
     else return a%2 ? b<a : a<b; 
} 
int main() 
{ 
     int a[] = {1,4,5,2,3,6,7}; 
     size_t N = sizeof(a)/sizeof(a[0]); 

     std::sort(a, a+N, Order); 

     for(size_t i=0; i<N; ++i) 
       std::cout << a[i] << ' '; 
     std::cout << std::endl; 

} 

Answer 2

// Sort with a custom comparison function 
// returns -1 if a before b, 0 if a==b, 1 if a after b 
int _cmp(a,b) { 
    if (a % 2) == 0 { 
    if (b % 2) == 0 { 
     return (a>b) ? 1 : (a==b) 0 : -1; # Even(a) vs Even(b) 
    } else { 
     return 1; # Even(a) vs Odd(b) all evens are after all odds 
    } 
    } else { 
    if (b % 2) == 0 { 
     return -1; # Odd(a) vs Even(b) all odds are before all evens 
    } else { 
     return (b>a) ? 1 : (a==b) 0 : -1; # Odd(a) vs Odd(b) has reverse order 
    } 
    } 
} 

Answer 3

Вот с # один вкладыш:

int[] x = { 1,4,5,2,3,6,7 }; 
Array.Sort(x, (a, b) => a % 2 == 0 ? b % 2 == 0 ? a.CompareTo(b) : 1 : b % 2 == 0 ? -1 : -1 * a.CompareTo(b)); 

Не превращайте его к своему учителю. Ваш учитель хочет, чтобы вы сами реализовали алгоритм сортировки, поэтому он знает, что вы можете это сделать, и знает, что вы понимаете, что связано с этим.

На практике вы почти никогда не будете делать это на работе. У вашей платформы уже есть высоко оптимизированные методы сортировки, и вы хотите использовать их, будь то C# Array.Sort() или .OrderBy() или алгоритм C++ stl. Этот код должен был показать вам, как вы могли бы решить эту проблему в реальном мире, хотя, если бы я хотел, чтобы это прошло проверку кода, я бы не смог сжать все это на одной строке.

Answer 4

С целыми числами в качестве цели сортировки вы можете получить это для сортировки O (n), используя сортировку count и немного осторожность.

Answer 5

Просто чтобы дать альтернативное решение:

#include <algorithm> 
#include <functional> 

bool is_odd(int x) 
{ 
    return x & 1; 
} 

int* rushakoff(int* begin, int* end) 
{ 
    int* middle = std::partition(begin, end, is_odd); 
    std::sort(begin, middle, std::greater<int>()); 
    std::sort(middle, end, std::less<int>()); 
    return middle; 
} 

int main() 
{ 
    int array[] = {1,4,5,2,3,6,7}; 
    rushakoff(array, array + 7); 
} 

Может быть, не так оптимально, но вполне читаемым. Это тоже важно ;-)