我认为使用标准的C函数qsort就足够了。
这是一个演示程序。

#include <stdio.h>
#include <stdlib.h>

int cmp_numbers( const void *a, const void *b )
{
    unsigned int x = *( const unsigned int * )a;
    unsigned int y = *( const unsigned int * )b;

    int result = ( int )( x % 2 ) - ( int )( y % 2 );

    if (result == 0)
    {
        enum { Even = 0, Odd = 1 };

        switch (x % 2)
        {
        case Even:
            return ( y < x ) - ( x < y );
        case Odd:
            return ( x < y ) - ( y < x );
        }
    }
    else
    {
        return result;
    }
}

int main( void )
{
    unsigned int a[] = { 8, 1, 6, 3,  4, 5, 2, 7, 0,  9 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for (size_t i = 0; i < N; i++)
    {
        printf( "%u ", a[i] );
    }
    putchar( '\n' );

    qsort( a, N, sizeof( *a ), cmp_numbers );

    for (size_t i = 0; i < N; i++)
    {
        printf( "%u ", a[i] );
    }
    putchar( '\n' );
}

程序输出为

8 1 6 3 4 5 2 7 0 9
0 2 4 6 8 9 7 5 3 1

否则，您可以编写一个函数，将数组拆分为两个分区，并分别对分区进行排序。
注意这个孤独的

int result = ( int )( x % 2 ) - ( int )( y % 2 );

如果不强制转换为int，表达式的结果将是unsigned int（x和y的类型），并且永远不能为负。
如果你想拥有一个有符号整数数组，那么除了在这个语句中从无符号整数到整数的其他变化之外，使用标准的C函数abs

int result = abs( x % 2 ) - abs( y % 2 );