C++坐标排序不符合预期问题求助

嘿，我来帮你排查这个排序问题～

首先，你的核心问题出在分两次调用sort的思路，以及第二个比较函数的逻辑错误上。

你先按x升序排好了数组，然后又调用sort用comparey函数。但这个comparey函数只有当两个元素x相等且a的y更小时才返回true，其他情况都返回false。这就导致：对于x不同的元素，sort会认为它们的顺序“谁在前谁在后都可以”（因为comparey(a,b)和comparey(b,a)都返回false），而std::sort不是稳定排序，它会重新打乱这些元素的顺序，直接破坏了你第一次按x排好的结果——这就是为什么最后x=3的元素里，y的顺序变成了2、3、1，完全不符合预期。

而且你还犯了一个小错误：sort(v+1, v+n)的范围不对！std::sort的第二个参数是尾后迭代器，也就是说这个范围是[first, last)，不包含last指向的元素。你要排序v[1]到v[n]，应该写成sort(v+1, v+1 + n)，不然最后一个元素v[n]根本没被排序进去。

解决方法 #

其实根本不需要两次排序，只需要一个比较函数就能实现“先x升序，x相等时y升序”的规则：

1. 写一个正确的比较函数：

bool compare(coord a, coord b){
    // 先比x坐标，x小的排在前面
    if (a.x != b.x) {
        return a.x < b.x;
    }
    // x相等的情况下，再比y坐标，y小的排在前面
    return a.y < b.y;
}

2. 替换掉原来的comparex和comparey，然后只调用一次sort，注意范围：

修改后的完整代码：

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

typedef struct{
    short x;
    short y;
} coord;

bool compare(coord a, coord b){
    if (a.x != b.x) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

int main(){
    short n;
    coord v[1001];
    while(cin >> n){
        for (int i=1; i<=n; i++){
            cin >> v[i].x;
            cin >> v[i].y;
        }
        // 正确排序范围：包含v[1]到v[n]
        sort(v+1, v+1 + n, compare);
        for (int i=1; i<=n; i++){
            cout << v[i].x << ' ' << v[i].y << endl;
        }
    }
    return 0;
}

这样运行后，就能得到你预期的排序结果了。

补充说一句：如果非要分两次排序（完全没必要），你需要用std::stable_sort，并且第二次的比较函数要保证x不等时不改变原有顺序，但这样做既低效又容易出错，不如一次排序来得直接可靠。

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