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;
}
这其实是将一个偏序关系全序化,容易理解这个比较函数包含了前面那个比较函数的内容。
分享到:
相关推荐
主要设计CreateUDG函数创建图的邻接链表,其中通过LocateVex 可以定位到邻接表代表元素的数组下标并进行连接TopologicalSort函数调用链栈对图的所有结点进行拓扑排序的功能,并为计算最晚开始时间做准备, ...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_DIJ函数...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_DIJ函数...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_DIJ函数...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_DIJ函数...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_...
范例1-108 拓扑排序 366 ∷相关函数:TopologicalSort函数 1.7.8 关键路径 374 范例1-109 关键路径 374 ∷相关函数:CriticalPath函数 1.7.9 最短路径 383 范例1-110 最短路径 383 ∷相关函数:ShortestPath_...
右下显示拓扑排序过程中入度为零的顶点的栈S,右上显示的栈 T 存放拓扑序列,其入栈顺序和栈 S 的出栈顺序相同,从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果,其中红色字体...
拓扑排序 数据结构 链接列表:单,双,循环 位图 队列 堆 双端队列 哈希表:单独链接,线性探测,哈希函数 哈希图 哈希集 设置(接口) 地图(接口) 树木:AVL树,红黑树,二叉树,二叉搜索树,生成树 图(无向,...
对给定的文件进行拓扑排序 tty 显示标准输出设备连接终端的文件名 uname 打印系统信息 unexpand 把空格符转换成 tab uniq 抛弃指定文件或者标准输入中内容重复的行 unlink 删除指定文件 users 显示在...
主题包括深度优先搜索、广度优先搜索、拓扑排序、Kosaraju-Sharir、Kruskal、Prim、Dijkistra、Bellman-Ford、Ford-Fulkerson、LSD 基数排序、MSD 基数排序、3 路基数快速排序、多路尝试、三元搜索尝试、Knuth-...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(short...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
4.4.1 域名服务器后台进程工具的使用......................................................................................12 4.4.1.1 诊断工具................................................................