void sort(int *x, int *y)
{
  bool a = *x & 1;
  bool b = *y & 1;
  bool c = *x < *y;
  if (a && !b) swap(*x, *y);
  else if (!a && !b && c) swap(*x, *y);
  else if (a && b && !c) swap(*x, *y);
}

#define swap(x,y) s = x; x = y; y = s;

#define N 19

int main()
{
    int s;
    int i = 0;
    int j = N-1;

// Шаг №1:
    do {
        while ((rnd[i]%2 == 0)&&(i != j)) i = i + 1;
        while ((rnd[j]%2 == 1)&&(j != i)) j = j - 1;
        swap(rnd[i],rnd[j]);
    } while (i != j);

// Шаг №2:
    if (1 < i)
    {
        if (rnd[N-1]%2 == 0)  i = i + 1;

        сортировка_первых_i_значений_rnd[]_по_убыванию
    }

// Шаг №3:
    if (j < N-1)
    {
        сортировка_последних_N-j_значений_rnd[]_по_возрастанию
    }

    return 0;
}

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace VS_2017_ArraySort {

public class myComparer : IComparer {

public int Compare(object x, object y ) {
if (x == y) return 0;
else if (((int)x % 2) == 1 && ((int)y % 2) == 0) return 1;
else if (((int)x % 2) == 0 && ((int)y % 2) == 0 && ((int)x < (int)y)) return 1;
else if (((int)x % 2) == 1 && ((int)y % 2) == 1 && ((int)x > (int)y)) return 1;
else return -1;
}
}

class Program {
static void Main(string[] args) {
IComparer myComp = new myComparer();

const int N = 20;
int[] Arr = new int[N];
Random Rnd = new Random();

for (int i=0; i<N; i++) {
Arr[i] = Rnd.Next(0, 99);
}
Console.Write("Исходный массив: ");
foreach (int i in Arr)
Console.Write(i + " ");
Console.WriteLine();

Array.Sort(Arr, myComp);
Console.Write("После сортировки: ");
foreach (int i in Arr)
Console.Write(i + " ");
Console.WriteLine();
}
}
}

/* Quicksort setup function. */
void quick(char *items, int count)
{
  qs(items, 0, count-1);
}  
/* The Quicksort. */
void qs(char *items, int left, int right)
{
  register int i, j;
  char x, y;
  i = left; j = right;
  x = items[(left+right)/2];
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}