c – STL排序进入无限循环?

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define PR(x) cout << #x " = " << x << "\n";


struct bomb
{
    int x,  y, state;
    bomb(){
        state = 1;
    }
};

bool cmpX(const bomb a,const bomb b){

    if(a.x == b.x){
        int t1 = a.y<0?(-a.y):a.y;
        int t2 = b.y<0?(-b.y):b.y;
        printf("%d %d\n",t1,t2 ); // to check this func
        if(t1>t2) return false;
        else return true;

    }
    int t1 = a.x<0?(-a.x):a.x;
    int t2 = b.x<0?(-b.x):b.x;
    printf("%d %d\n",t1,t2 ); // to check this func
        if(t1>t2) return false;
        else return true;

}


int main(){
    int n;

    cin>>n;
    bomb s[100000];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d",&s[i].x, &s[i].y);
    }
    sort(s,s+n,cmpX);
}    

此代码将在以下输入上进入无限循环:
    24
    -2 -2
    -1 1
    0 1
    1 1
    0 2
    1 -1
    2 -2
    1 -2
    -1 0
    0 -2
    0 -1
    -2 0
    -2 -1
    2 -1
    2 2
    -1 -2
    -2 1
    2 0
    -1 2
    1 2
    -1 -1
    1 0
    2 1
    -2 2

以下是ideone链接:
http://ideone.com/x1Gbah

解决方法:

您需要定义严格的弱排序,这意味着如果元素相同则需要返回false.要解决这个问题,请更改

if(t1>t2)

if(t1>=t2)
上一篇:各种各样的排序(集合篇)-java代码


下一篇:Ultra-QuickSort(离散化)