题解 第三章排序与查找| #整数奇偶排序#

使用了奇偶划分的方法

将奇数和偶数进行了划分

从而得到了数组左右两列分别为奇数和偶数

#include <stdio.h>
#include <stdlib.h>
#define Num 10
//思路类比划分(快速排序)
//将其分类为左奇,右边偶的状态

int DivideParity(int Arr[])
{ //左边为奇,右边为偶数
    int temp=Arr[0];
    int i=0,j=Num-1;
    while(i<j)
    {
        while(!(Arr[j]%2)) j--;
        if(i>j)
            break;
        Arr[i++]=Arr[j];
        while(Arr[i]%2) i++;
        if(i>j)
        {
            i--;
            break;
        }
        Arr[j--]=Arr[i];
    }
    Arr[i]=temp;
    if(temp%2)
        return i; //返回奇数的最后一位的数组编号
    return i-1;
}

int cmpD(const void* a,const void *b)
{
    return *((int *)a)>*((int *)b);
}

int cmpX(const void* a,const void *b)
{
    return *((int *)a)<*((int *)b);
}


int main()
{
    int Arr[Num];
    while (scanf("%d", &Arr[0]) != EOF)
    {
        for (int i = 1; i < Num; i++)
            scanf("%d", &Arr[i]);
        //如此将所有数据存入数组

        int Div = DivideParity(Arr);

        qsort(Arr, Div+1, sizeof(int),cmpX);
        qsort(Arr + Div+1, Num - Div-1, sizeof(int),cmpD);

        for (int i = 0; i < Num; i++)
            printf("%d ", Arr[i]);
        printf("\n");
    }
    return 0;
}