chapter3-排序和查找

1.排序

排序就是把一组无序的数据变成有序的过程。对于机试而言，直接使用C++封装好的sort函数就可以了。sort函数内部采用快速排序实现，因此非常高效。使用sort函数，需要引用#include <algorithm>头文件，sort(first_address, last_address, compare)有三个参数，first和last待排序序列的起始地址和结束地址；compare为比较方式。如果不规定第三个参数，则默认是从小到大升序方式。
注意，1、sort函数的地址是左闭右开区间的。2、如果要对给定的数组进行降序排列或以自定义的方式排列，那么第三个参数会起作用。可以通过编写比较函数的方式来实现想要的自定义排序方式。

排序，既包括对内部已经定义的基本数据类型的排序，如整型、字符型等，也包括对自定义数据类型的排序，如结构体或者类。所以要注意，整数是有大小关系的，而结构体变量本身是没有大小关系的，sort函数的默认排序方式无法满足要求，必须依据题面描述写一个自定义的函数才能完成上述要求。
考生在遇到新的排序规则时，只需记住如下这条黄金法则：当比较函数的返回值为true时，表示的是比较函数的第一个参数将会排在第二个参数前面。
所有的比较，最终还是要转换成为对于大小的比较，奇偶性就是考察模2之后值的大小比较，一切比较都是基于两个数之间如何定义它们的大小关系，找出内部的大小关系，设计出合格的Compare比较函数。

1.1整数奇偶排序

//排序-习题3.2 整数奇偶排序 2024-02-09
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN=10+2;
int arr[MAXN];
//自定义比较函数，确定谁在前谁在后
bool compare(int a, int b)
{
    if(a%2 == 1 && b%2 == 1)
    {
        return b < a;
    }else if (a%2 == 0 && b%2 == 0)
    {
        return a < b;
    }else if (a%2 == 1 && b%2 == 0)
    {
        return true;
    }else{//情况4：a为偶数，b为奇数
        return false;
    }
}

int main()
{
    while(scanf("%d", &arr[0]) != EOF)
    {
        for(int i=1; i<10; i++)
        {
            scanf("%d", &arr[i]);
        }
        sort(arr, arr + 10, compare);//注意：sort函数的地址参数是左闭右开的

        for(int i=0; i<10; i++)
        {
            printf("%d", arr[i]);
            if(i != 9)
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}