施用sort进行拓扑排序的比较函数

使用sort进行拓扑排序的比较函数

C++等语言自带的sort函数使用的排序算法基本都是快速排序，快速排序是一种不稳定的排序算法，也就是说两个相等的元素排序前后的相对位置是有可能变化的。在使用sort对一个有偏序关系的序列进行拓扑排序时，比较函数的设计要特别注意。例如我们对格点（x,y）进行排序，使得如果有x0 <=?x1 而且 y0 <= y1时，（x0,y0）在（x1,y1）前面。

?

代码大致如下：

?

const int N = 10;struct Node {int x, y;void init(int _x, int _y) {x = _x;y = _y;}}node[N * N];bool cmp(const Node &a, const Node &b) {}int main() {int n = 0;for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {node[n++].init(i, j);}}for (int i = 0; i < N * N; ++i) {swap(node[i], node[rand() % (N * N)]);}sort(node, node + n, cmp);for (int i = 0; i < N; ++i) {printf("%d %d\n", node[i].x, node[i].y);}return 0;}

?非常直观地，也许我们会把比较函数设计成：

bool cmp(const Node &a, const Node &b) {return a.x <= b.x && a.y <= b.y;}

?

但是这样的结果很可能不是我们所要的，我们确定了这么个比较关系之后，所有不满足的这个关系的两个元素进来比较，都会被认为第一个应该在第二个后面。

?

正确的，应该设计成这样：

bool cmp(const Node &a, const Node &b) {return a.x < b.x || a.x == b.x && a.y < b.y;}

?

这其实是将一个偏序关系全序化，容易理解这个比较函数包含了前面那个比较函数的内容。