如何在 Python3 中对列表 通过比较排序（不懂就问）？

[superhxl]

已知列表和字典，列表是需排序元素，字典指明了元素间的优先关系，譬如 S1 需在 S3 之前，而 S3 又在 S2 之前。

s = ['S1','S2','S3']

val = {('S1','S3'):1,('S3','S2'):1}

希望得到的结果是['S1','S3','S2']，请问有何好的实现方式？

自己想用 python 中的 sort 的 cmp 参数进行排序，结果竟然没排序，不知原因。

from functools import cmp_to_key

 s.sort(key=cmp_to_key(lambda x,y: val.get((x,y),0)))

[toaruScar]

可以弄成一个 class，然后用 functools.total_ordering 自定义对比函数。

[MoYi123]

s = ['S1', 'S2', 'S3']
val = {('S1', 'S3'): 1, ('S3', 'S2'): 1}


class S(str):

____def __lt__(self, other):
________if (self, other) in val:
____________return val[(self, other)] == 1
________return False


s = [S(i) for i in s]
s.sort()
print([str(i) for i in s])

能用， 但是应该有更好的办法

[Trim21]

key=lambda x: {s1: 1 , s3: 2, s3: 3}.get(x, 0)

[lonelinsky]

s = ['S1','S2','S3']
val = {('S1','S3'):-1,('S3','S2'):-1} # 这里你一开始的定义有点问题，如果你希望 S1 排在 S3 前面，则它的值应该是负的

s.sort(key=cmp_to_key(lambda x,y: val.get((x,y), -val.get((y,x), 0)))) # 这里你可能需要同时处理 (y, x) 的情况，如果你的定义是对称的。即 S1 在 S3 前面 <=> S3 在 S2 后面

注意你现在的方式里面对于未出现 val 里面的对，都会当成不需要排序的对象。如果你是像解决 AOE 网络的拓扑排序问题，建议直接看相关算法。

=============================
你一开始的排序完全没用是因为排序时候，假设按序比较
(S1, S2) 你的 val 里面没有，返回 0 表示相等，不用做任何操作
(S2, S3) 你的 val 里面还是没有，返回 0 表示相等，又不用做任何操作，所以它已经排好序了

[lonelinsky]

typo
S1 在 S3 前面 <=> S3 在 S1 后面

[superhxl]

@lonelinsky 我的定义没问题，也许有更好的方式。本身问题背景是若干个点，一次对这些点遍历，想要打印遍历的顺序。字典中的值表示相继访问的顺序，访问 S1 后访问 S3，访问 S3 后访问 S2.

关于 cmp 的应用再查查文档，这个确实是临时搜索的解决方案。

目前可以通过冒泡排序解决，但我想应该有更好办法。
```python
for p in range(len(s)-1):
for q in range(p + 1, len(s)):
if sol[z[(s[q],s[p])]] == 1:
s[p], s[q] = s[q], s[p]
```
@toaruScar 去学习一下具体用法。
@MoYi123 好复杂的样子。
@Trim21 没看懂。

[lonelinsky]

https://docs.python.org/3/library/functools.html#functools.cmp_to_key
A comparison function is any callable that accept two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than.

你定义的 1 会被认为是 greater-than，而默认排序是从小到大，所以你的定义和你的预期是反的，这是我说你定义有问题的地方，如果执意用 1 做定义的话，可以在 function 里面取个反就行。
你现在的定义里面不能保证任意两个元素的 cmp 结果都包含，比如你开始的定义里面 S1 和 S2 的大小关系没有显式定义，在冒泡这种会完全比较的排序方法中可能没问题，但是对于类似快排这种，排序中间可能会出现错误的结果。(这个地方是直觉，没有严格证明）

> 本身问题背景是若干个点，一次对这些点遍历，想要打印遍历的顺序。
如果是这个问题的话，建议用 OrderedDict https://docs.python.org/3/library/collections.html#collections.OrderedDict，直接打印就好了。

[lonelinsky]

> 字典中的值表示相继访问的顺序
我好像理解错了，所以字典中的值会是 1，2，3 这样？是的话对字典按 value 排序，然后对 key 做个 reduce 就好了？

[BBrother]

没看到你的问题，你是不是需要拓扑排序？

[princelai]

from networkx import DiGraph, draw_networkx, topological_sort

s = ['S1', 'S2', 'S3', 'S4', 'S5']
val = {('S1', 'S3'): 1, ('S3', 'S2'): 1, ('S5', 'S1'): 1, ('S2', 'S4'): 1}
g = DiGraph()
g.add_edges_from(val.keys())
s = list(topological_sort(g))

[ipwx]

@superhxl python 默认的不是两两比较排序，而是快速排序，只比 N log N 次。

所以你期待的 S1 < S3 + S3 < S2 imply S1 < S2 不存在。

你这个需求可以建图然后用拓扑排序。

[Pythoner666666]

老谢 是你吗？？

[O5oz6z3]

想到一个麻烦的做法：
def cmp(a, b):
　 lt = val.get((a,b))
　 if lt == 1:
　　 return -1
　 gt = val.get((b,a))
　 if gt == 1:
　　 return 1
　 return -1 if a<b else 1 if a>b else 0
感觉像 #10 楼那样将 val 换成 set(val.keys()) 也没有问题。这个自定义排序似乎可以再加些功能，比如优先度排序？

[efaun]

@MoYi123 #2 缩进的下划线是你手动加的还是有工具？

[MoYi123]

@efaun 手动的

[superhxl]

@lonelinsky 明白了，多谢！对 collections 模块缺失不熟悉！

@princelai networkx 听说过，但没用过。果然学无止境。本来自己把顺序提取出来，就是为了绘图，采用 networkx 直接帮我把问题全解决了。

@Pythoner666666 ☻，认错人了！

感谢楼上所有帮忙出注意的 V 友！