C++对象数组排序重复值按用户优先级多条件排序 求高效低内存方案

现有代码存在的问题 #

• 三次全量排序的逻辑错误：后执行的排序会直接破坏高优先级字段的排序结果，比如先按age排序，再全量按height排序，最终结果是按height为主序排序，age的排序结果完全被覆盖
• 插入排序时间复杂度为O(n²)，数据量稍大时性能极差
• 没有实现同字段重复时的次级排序逻辑

最优实现方案 #

采用单次排序+自定义多级比较器的方案，完全满足「运行速度最快、内存占用最低」的要求，优势如下：

• 仅执行一次排序操作，时间复杂度为O(nlogn)，远优于多次排序的时间开销
• 使用标准库的std::sort原地排序，额外内存开销仅为O(logn)的调用栈空间，无额外堆内存占用
• 无需手动定位重复值、拆分分组，所有多级排序逻辑全部收敛到比较器中，实现简单不易出错

修改后的完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

class Person{
public:
    string name;
    int age;
    int weight;
    int height;
};

// 全局存储排序优先级，供比较器使用
int sortOrder[3];

bool comparePerson(const Person& a, const Person& b) {
    for(int i=0; i<3; i++) {
        int fieldA, fieldB;
        switch(sortOrder[i]) {
            case 1: 
                fieldA = a.age; fieldB = b.age;
                break;
            case 2: 
                fieldA = a.height; fieldB = b.height;
                break;
            case 3: 
                fieldA = a.weight; fieldB = b.weight;
                break;
            default: 
                fieldA = 0; fieldB = 0;
        }
        if(fieldA != fieldB) {
            return fieldA > fieldB; // 保持原代码降序排序的逻辑
        }
    }
    // 三个字段全部相等时保持原有相对顺序
    return false;
}

int main()
{
    int n;
    cin >> n;

    Person * people = new Person[n];

    for(int i = 0; i < n; i++) {
        cin >> people[i].name >> people[i].age >> people[i].weight >> people[i].height;
    }
    cout << endl << endl;

    cout << "Enter the order of sorting, choose numbers form 1 to 3, where 1 is sorting by Age, 2 is sorting by Height and 3 is sorting by weight \n";
    cin >> sortOrder[0] >> sortOrder[1] >> sortOrder[2];

    // 单次排序完成所有多级排序逻辑
    sort(people, people + n, comparePerson);

    // 可在此处添加输出逻辑验证排序结果
    for(int i=0; i<n; i++) {
        cout << people[i].name << " " << people[i].age << " " << people[i].height << " " << people[i].weight << endl;
    }

    delete [] people;
    return 0;
}

可选补充方案 #

如果确实需要按照「先排主字段，再仅对重复分组排次级字段」的逻辑实现，可参考如下思路：

1. 第一次按主字段完成全量排序
2. 遍历数组，找到所有主字段值相同的连续区间[left, right]
3. 对每个[left, right]区间按次级字段排序
4. 再在每个次级字段相同的子区间内按第三字段排序
   该方案实现复杂，多次子区间排序的常数开销远高于单次多级排序，仅在主字段重复率极低的场景下有微弱性能优势，绝大多数场景下不推荐使用。

内容的提问来源于stack exchange，提问作者Filgum0326