全国青少年信息素养大赛：排序专项：奇偶排序

我们要将一个数组分成前半部分奇数、后半部分偶数，并将前后两部分各自从小到大排序。

【输入格式】

第一行输入一个整数n(n≤100)。

第二行输入 n 个整数。

【输出格式】

输出 n 个数，前半部分奇数(从小到大排序)、后半部分偶数(从小 到大排序)。

     

【样例输入】

10

9  6  4  3  5  1  7  10  8  2

【样例输出】

1  3  5  7  9  2  4  6  8  10

【参考程序一】

#include<bits/stdc++.h>
using namespace std;

int a[101];
int main()
{
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; 
	 } 
	 
	 sort(a,a+n);
	 
	for(int i=0;i<n;i++)
	{
		if(a[i]%2!=0)
		{
			cout<<a[i]<<" "; 
		}
	 }
	for(int i=0;i<n;i++)
	{
		if(a[i]%2==0)
		{
			cout<<a[i]<<" "; 
		}
	 }
	 	 
	return 0;
 } 

【参考程序二】

#include<bits/stdc++.h>
using namespace std;

int a[101];
bool comp(int a,int b)
{
	if((a%2==0&&b%2==0)||(a%2!=0&&b%2!=0))
	{
		return a<b;
	}
	
	if(a%2==0&&b%2!=0)
	{
		return false;
	}
	
	if(a%2!=0&&b%2==0)
	{
		return true;
	}
}

int main()
{
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; 
	 } 
	 
	 sort(a,a+n,comp);
	 
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" "; 
	 }
 
	return 0;
 } 

在 comp 函数中，定义了比较规则：

• 如果两个数都是奇数或者都是偶数，按照从小到大的顺序比较。

• 如果一个是偶数一个是奇数，偶数排在奇数后面。

sort 函数根据这个比较规则对数组进行排序，从而实现了题目要求。

例如，输入 5 和 1 2 3 4 5 ，排序后输出将是 1 3 5 2 4 。 又比如输入 6 和 2 4 6 1 3 5 ，排序后的输出将是 1 3 5 2 4 6 。

【参考程序三】

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int odd[n], even[n];
    int oddCount = 0, evenCount = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1) {
            odd[oddCount++] = arr[i];
        } else {
            even[evenCount++] = arr[i];
        }
    }

    // 对奇数数组排序
    for (int i = 0; i < oddCount - 1; i++) {
        for (int j = 0; j < oddCount - i - 1; j++) {
            if (odd[j] > odd[j + 1]) {
                int temp = odd[j];
                odd[j] = odd[j + 1];
                odd[j + 1] = temp;
            }
        }
    }

    // 对偶数数组排序
    for (int i = 0; i < evenCount - 1; i++) {
        for (int j = 0; j < evenCount - i - 1; j++) {
            if (even[j] > even[j + 1]) {
                int temp = even[j];
                even[j] = even[j + 1];
                even[j + 1] = temp;
            }
        }
    }

    int oddIndex = 0, evenIndex = 0;
    for (int i = 0; i < n; i++) {
        if (oddIndex < oddCount) {
            arr[i] = odd[oddIndex++];
        } else {
            arr[i] = even[evenIndex++];
        }
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

【参考程序四】

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<int> odd, even;
    for (int num : arr) {
        if (num % 2 == 1) {
            odd.push_back(num);
        } else {
            even.push_back(num);
        }
    }

    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());

    int oddIndex = 0, evenIndex = 0;
    for (int i = 0; i < n; i++) {
        if (i < odd.size()) {
            arr[i] = odd[oddIndex++];
        } else {
            arr[i] = even[evenIndex++];
        }
    }

    for (int num : arr) {
        cout << num << " ";
    }

    return 0;
}

在上述代码中，我们首先读取输入的整数个数 n 和数组元素。然后将数组中的奇数和偶数分别存储在两个不同的向量 odd 和 even 中，并对它们进行排序。接下来，通过两个指针 oddIndex 和 evenIndex ，将排序后的奇数和偶数重新放回原数组中，从而实现题目要求。例如，如果输入 5 和 3 4 5 2 1 ，那么奇数为 3, 5, 1 ，排序后为 1, 3, 5 ；偶数为 4, 2 ，排序后为 2, 4 ，最终输出为 1 3 5 2 4 。