C++ 代码

利用快速排序算法的模板

1. 首先将原始的数组读取进来，记为q[]
2. 然后分别将q[]数组的奇数和偶数对应的下标记录下来，存在新的数组里面e[]和o[]
3. 然后分别对q[]的e[]下标以及o[]下标进行排序
4. 输出

# include <iostream>
using namespace std;
const int N = 1010;
int n, m, q[N], o[N], e[N];

void quick_sort_up(int q[], int o[], int l, int r)
{
    if (l >= r) return;
    int x = q[o[l + r >> 1]], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while (q[o[i]] < x);
        do j --; while (q[o[j]] > x);
        if(i < j) swap(q[o[i]], q[o[j]]);
    }
    quick_sort_up(q, o, l, j), quick_sort_up(q, o, j + 1, r);
}

void quick_sort_down(int q[], int e[], int l, int r)
{
    if (l >= r) return;
    int x = q[e[l + r >> 1]], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while (q[e[i]] > x);
        do j --; while (q[e[j]] < x);
        if(i < j) swap(q[e[i]], q[e[j]]);
    }
    quick_sort_down(q, e, l, j), quick_sort_down(q, e, j + 1, r);
}

int main()
{
    scanf("%d", &m);
    for (int k = 0; k < m; k ++)
    {
        scanf("%d", &n);
        // 分别作为奇数和偶数的idx
        int idxo = 0, idxe = 0;

        for (int i = 0; i < n; i ++ )  
        {
            scanf("%d", &q[i]);
            // 记录奇数和偶数对应的下标
            if(q[i] % 2 == 0) e[ idxe++] = i;
            else o[ idxo++] = i;
        }
        // 快速排序
        quick_sort_up(q, o, 0, idxo - 1);
        quick_sort_down(q, e, 0, idxe - 1);

        printf("Case #%d: ", k + 1);
        for (int i = 0; i < n; i ++) printf("%d ", q[i]);
        puts("");
    }
    return 0;
}