※ 引述《KSJ (阿真)》之铭言： : 也参考过回文的文章 跟参考文章 : 对於以下的解释还是不解(虽然会使用了) : 想请板友们帮个忙： : : " : key 的使用方式比前面 cmp 的方式来的直觉，而且速度较快， : 因为排序的时候，只要需要比较的动作就会呼叫 cmp， : 而 key 只会被呼叫 n 次，n 是序列的长度，所以 key 的速度较快。 : " : : 我的想法是 : 比方有三个数 [小 ,大 ,中] : cmp感觉是 先抓 小 大 二个比 把小放在第一位 : 再抓 大 中 二个比 : 再抓 小 中 二个比 把中放在第二位 : 把大放在第三位 : 二个疑问： : 1. 对於key的比法(还是说 应该称作 "准则") 是类似cmp这样吗?怎麽比的呢？ 直接拿 key 与 cmp 参数来比较是不太适当的，因为两者负责的工作(任务)不同， 且二者不是互斥的。 cmp 参数的责任是指出任两个 element(a, b) 的大小： -1 for a < b 0 for a == b 1 for a > b 如果 list element 本身就是 comparable(有 natural order)，而你想要 list 排序的顺序就是依照 natural order，你可以不需要提供 cmp 参数。 如果你想要依照 natural order 以外的规则来排序，或者是 list element 本身 不是 comparable(比如 element 是一种复合的结构)，那麽就需要提供 cmp 参数。 以 element 为复合的结构为例，自行提供的 cmp function 依照某种逻辑来决定 大小关系。比如说 list element 为 tuple，这些 tuple 皆是升幂排列的整数 数列，我希望将这些 tuple 依照其 maximum 来升幂排序。 A=[(2, 4, 6, 8), (1, 3, 5), (1, 2, 4)] A.sort(cmp=lambda a, b: cmp(a[-1], b[-1])) print A # [(1, 2, 4), (1, 3, 5), (2, 4, 6, 8)] 在不搭配 key 参数的情况下，cmp 参数带进来的 function 在面对复合型态的 物件时，通常要做两件事： 1.从两个 object 中撷取主导排序的数据 2.决定撷取出来的数据的大小 在 list.sort 执行过程中(不论 list.sort 实际上是使用哪一种排序演算法)，当 有需要比较某两个 element 时，cmp 参数带进来的 function 都会被执行一次。 key 参数负责的任务是从 element 撷取出主导 element 顺序的关键数据，取出来的 关键数据必须是 comparable。 延续前面的例子： A=[(2, 4, 6, 8), (1, 3, 5), (1, 2, 4)] A.sort(key=lambda s: s[-1]) print A # [(1, 2, 4), (1, 3, 5), (2, 4, 6, 8)] 这种作法是先把一个 object sequence 经过一个 mapping 变成另一个 object sequence(两个 object sequence 对应的 element 有关连)，然後以後者来做 sorting。 [2 4 6 8] [1 3 5] [1 2 4] <=== A | | | | | | <== map(lambda s:s[-1], A) | | | 8 5 4 <=== B ↓ sort B 4 5 8 <=== sorted B | | | [1 2 4] [1 3 5] [2 4 6 8] <=== sorted A 所以在这种排序复合元素的情况下，通常指定 key 参数会比较有效率，因为 cmp 参数指定的 function 每次在决定元素大小前都要做一次撷取关键数据的 动作，而 key 参数指定的 function 是一开始拿来将每个元素的关键数据取出， 之後进行排序时就不再使用到。 如果 key 参数(function)撷取的数据的 natural order 不同你想要的顺序， 可再搭配 cmp 参数。 : 2. 又对於最原本的sort()方法 是用最佳化的比法 还是最简单的比法呢?? 有没有客制 cmp or key function，list.sort 使用的排序演算法都是一样的。 我猜 list.sort 应该是使用 quicksort 变化而来的演算法，可能在 list size 够小时是使用其他的排序演算法，size 大时使用 quicksort。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.173.137.110 ※ 编辑: sbrhsieh 来自: 218.173.137.110 (11/20 15:05)