qsort 用于对对象数组进行排序

Question

我正在尝试使用 qsort() 对对象指针数组进行排序（PointP = Point*） 附件是比较函数和排序，问题是什么也没有发生，排序也没有发生。

int compareByAngleP(const void* elem1,const void* elem2) {
    PointP point1 = (PointP) elem1;
    PointP point2 = (PointP) elem2;
    if (abs(point1->getAngle() - point2->getAngle())>0.001)
    {
        return point1->getAngle() - point2->getAngle();
    }
    return  point1->getY() - point2->getY();
}

void sortArrayP(PointP* array, int size) {
    qsort(array,size, sizeof(PointP), compareByAngleP);
}

Answer 1

我的建议是忘记

std::qsort

，喜欢普通的

std::sort

。与

std::qsort

不同，它是类型安全的，并且在大多数实现中速度更快。

std::sort(array, array+size, compareByAngleP);

并删除比较函数中的

void*

，以支持实际类型。

此外，如果您使用 C++11 并且数组只是本地数组：

std::sort(std::begin(array), std::end(array), compareByAngleP);

或者更好的是使用

std::vector

或其他最合适的容器。

std::vector<Point> array { ... };
std::sort(array.begin(), array.end(), compareByAngleP);

注意

您可能需要修改比较函数，以便在第一个参数小于第二个参数时返回 true。 （或者简单地为 Point 实现

operator <

）。

参考文献

http://en.cppreference.com/w/cpp/algorithm/sort

http://en.cppreference.com/w/cpp/container/vector

Answer 2

您使用

qsort

和比较功能时存在几个问题。

1. qsort

   将使用

   memcpy

   （或类似的）对数组的元素重新排序。如果您的

   Point

   类型具有复制构造函数（或具有复制构造函数的成员），则在其上使用

   qsort

   会带来麻烦（会导致未定义的行为）。

2. 您的

   compareByAngleP

   函数不适合排序，因为它检查的关系不具有传递性。 例如，如果您有三个点

   A

   、

   B

   和

   C

   ，它们都具有相同的

   Y

   坐标，并且分别具有角度

   10.000

   、

   10.001

   和

   10.002

   ，那么

   compareByAngeP

   将表示

   A == B

   和

   B == C

   ，但是

   A != C

   ，这可能会对排序功能造成严重破坏。

Answer 3

以下 qsort 参考（http://en.cppreference.com/w/cpp/algorithm/qsort）qsort 的第三个参数应该是“数组中每个元素的大小（以字节为单位）”，所以改为

qsort(array,size, sizeof(PointP), compareByAngleP);

尝试

qsort(array,size, sizeof(PointP*), compareByAngleP);

您还隐式地将 float 转换为 int （同时从比较函数返回值）。但是：

(int)0.2 == 0

Answer 4

我认为如果你从 Compare 函数返回 bool 而不是 int，那么会发生不同的情况。