用C++解决‘合影效果’排序题：从冒泡到STL sort的三种实战思路（附完整代码）

想象一下这样的场景：班级合影时，老师要求男生按身高从低到高站在前排，女生按身高从高到低站在后排。这个看似简单的排队问题，实际上蕴含着排序算法的精髓。今天我们就以这道经典的OJ题目为例，带你领略C++中排序算法的多样魅力。

1. 问题分析与基础解法

合影效果问题本质上是一个多条件排序问题。我们需要处理两类数据：男生身高（升序）和女生身高（降序）。对于初学者来说，最直观的解法就是将两类数据分开处理。

1.1 分离数据法

这种方法的核心思想是将输入数据按性别分流到两个不同的数组：

double male[45], female[45];
int mi = 0, fi = 0; // 计数器初始化

// 数据输入分流
for(int i = 0; i < n; ++i) {
    char gender[10];
    double height;
    cin >> gender >> height;
    if(gender[0] == 'm') {
        male[mi++] = height; // 男生数据
    } else {
        female[fi++] = height; // 女生数据
    }
}

1.2 分别排序与输出

分离数据后，我们可以对两个数组分别排序：

// 男生升序排序
sort(male, male + mi);

// 女生降序排序
sort(female, female + fi, greater<double>());

// 输出结果
for(int i = 0; i < mi; ++i) 
    cout << fixed << setprecision(2) << male[i] << ' ';
for(int i = 0; i < fi; ++i) 
    cout << fixed << setprecision(2) << female[i] << ' ';

提示：使用 greater<double>() 可以方便地实现降序排序，这比自定义比较函数更简洁。

2. 进阶解法：统一比较条件

当掌握了基础解法后，我们可以尝试更优雅的解决方案——通过自定义比较条件实现统一排序。

2.1 结构体定义

首先定义一个包含性别和身高的结构体：

struct Student {
    char gender[15];
    double height;
};

2.2 自定义比较函数

关键点在于设计一个能够处理所有情况的比较函数：

bool compare(const Student &a, const Student &b) {
    if(a.gender[0] == 'm' && b.gender[0] == 'm') {
        return a.height < b.height; // 男生升序
    } else if(a.gender[0] == 'f' && b.gender[0] == 'f') {
        return a.height > b.height; // 女生降序
    } else {
        return a.gender[0] == 'm'; // 男生在前
    }
}

2.3 运算符重载实现

更C++风格的做法是重载小于运算符：

struct Student {
    char gender[15];
    double height;
    
    bool operator<(const Student &other) const {
        if(gender[0] == 'm' && other.gender[0] == 'm') {
            return height < other.height;
        } else if(gender[0] == 'f' && other.gender[0] == 'f') {
            return height > other.height;
        } else {
            return gender[0] == 'm';
        }
    }
};

3. 手动实现排序算法

为了深入理解排序原理，我们尝试手动实现两种经典排序算法来解决这个问题。

3.1 冒泡排序实现

冒泡排序虽然效率不高，但实现简单，适合教学演示：

void bubbleSort(Student arr[], int n) {
    for(int i = 0; i < n-1; ++i) {
        for(int j = 0; j < n-i-1; ++j) {
            // 自定义比较条件
            bool shouldSwap = false;
            if(arr[j].gender[0] == 'm' && arr[j+1].gender[0] == 'm') {
                shouldSwap = arr[j].height > arr[j+1].height;
            } else if(arr[j].gender[0] == 'f' && arr[j+1].gender[0] == 'f') {
                shouldSwap = arr[j].height < arr[j+1].height;
            } else if(arr[j].gender[0] == 'f' && arr[j+1].gender[0] == 'm') {
                shouldSwap = true;
            }
            
            if(shouldSwap) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

3.2 插入排序实现

插入排序在小数据量时表现良好：

void insertionSort(Student arr[], int n) {
    for(int i = 1; i < n; ++i) {
        Student key = arr[i];
        int j = i - 1;
        
        while(j >= 0 && 
              ((arr[j].gender[0] == 'm' && key.gender[0] == 'm' && arr[j].height > key.height) ||
               (arr[j].gender[0] == 'f' && key.gender[0] == 'f' && arr[j].height < key.height) ||
               (arr[j].gender[0] == 'f' && key.gender[0] == 'm'))) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

4. 性能对比与选择建议

虽然题目数据量很小（n≤40），但了解不同方法的性能特点仍然很有价值。

4.1 时间复杂度分析

方法	最好情况	平均情况	最坏情况
STL sort	O(n log n)	O(n log n)	O(n log n)
冒泡排序	O(n)	O(n²)	O(n²)
插入排序	O(n)	O(n²)	O(n²)

4.2 实际应用选择

• 竞赛场景 ：优先使用STL sort+自定义比较，代码简洁高效
• 教学目的 ：手动实现排序算法有助于理解原理
• 特殊需求 ：如果需要稳定排序，可以考虑stable_sort

4.3 代码风格建议

1. 变量命名 ：使用有意义的名称（如studentList而非简单的arr）
2. 函数封装 ：将排序逻辑封装成独立函数
3. 注释清晰 ：特别是复杂比较逻辑处
4. 错误处理 ：添加基本的输入验证

// 良好的代码风格示例
struct PhotoMember {
    enum Gender { MALE, FEMALE };
    Gender gender;
    double height;
    
    bool shouldStandBefore(const PhotoMember &other) const {
        if(gender == MALE && other.gender == MALE) {
            return height < other.height;
        } else if(gender == FEMALE && other.gender == FEMALE) {
            return height > other.height;
        } else {
            return gender == MALE;
        }
    }
};

在实际教学中发现，学生最容易混淆的是比较条件的逻辑判断。建议先用自然语言明确规则，再转换为代码。例如："男生在前，女生在后；同性别时，男生矮在前，女生高在前"。