Python比较排序只比较邻居

Question

以下代码对对象列表进行排序。

我想要实现的是按照它们的值排序类型为'boring'的对象。我不关心他们在列表中的位置，但最后他们需要排序。我的代码只是比较邻居，因此最终仍然是错误的顺序。

需要应用哪种类型的排序算法才能正确排序？

class SortMe: 
    def __init__(self, type, value): 
     self.type = type 
     self.value = value 
    def __repr__(self): 
     return "<%s %s %s>" % (self.__class__.__name__, self.type, self.value) 

stack = (
    SortMe('fancy', 15), 
    SortMe('fancy', 3), 
    SortMe('boring', 3), 
    SortMe('boring', 1), 
    SortMe('fancy', 1), 
    SortMe('boring', 22), 
    SortMe('fancy', 22), 
    SortMe('fancy', 17), 
    SortMe('boring', 5), 
    ) 

def compare(a1, a2): 
    if a1.type == 'boring' and a2.type == 'boring': 
     if a1.value > a2.value: 
      return 1 
     elif a1.value < a2.value: 
      return -1 
     else: 
      return 0 
    else: 
     return 0 

stack = sorted(stack, cmp=compare) 

print '\n'.join(map(str, stack)) 

电流输出（无聊的顺序错误的对象）：

<SortMe fancy 15> 
<SortMe fancy 3> 
<SortMe boring 1> 
<SortMe boring 3> 
<SortMe fancy 1> 
<SortMe boring 22> 
<SortMe fancy 22> 
<SortMe fancy 17> 
<SortMe boring 5> 

预期输出（按正确的顺序无聊，位置无所谓）：

<SortMe fancy 15> 
<SortMe fancy 3> 
<SortMe boring 1> 
<SortMe boring 3> 
<SortMe fancy 1> 
<SortMe boring 5> 
<SortMe boring 22> 
<SortMe fancy 22> 
<SortMe fancy 17> 

或：

<SortMe fancy 15> 
<SortMe fancy 3> 
<SortMe fancy 1> 
<SortMe fancy 22> 
<SortMe fancy 17> 
<SortMe boring 1> 
<SortMe boring 3> 
<SortMe boring 5> 
<SortMe boring 22> 

左右。

Answer 1

不要使用cmp键，只需直接提取使用key函数来代替值：

sorted(stack, key=lambda v: v.value if v.type == 'boring' else None) 

主要生产：

>>> for sm in sorted(stack, key=lambda v: v.value if v.type == 'boring' else None): 
...  print sm 
... 
<SortMe fancy 15> 
<SortMe fancy 3> 
<SortMe fancy 1> 
<SortMe fancy 22> 
<SortMe fancy 17> 
<SortMe boring 1> 
<SortMe boring 3> 
<SortMe boring 5> 
<SortMe boring 22> 

你cmp重要途径仍然比较任何fancy时返回0SortMe对象与boring之一，无论他们在什么顺序，创建一个不一致的排序。比较在不同的类型，而不是两个对象时，你需要始终返回-1或1：

def compare(a1, a2): 
    if a1.type == 'boring' and a2.type == 'boring': 
     return cmp(a1.value, a2.value) 
    else: 
     # sort fancy before boring, reverse order 
     return cmp(a2.type, a1.type) 

，我重复使用cmp()内置函数返回合适-1，0或1值：

>>> def compare(a1, a2): 
...  if a1.type == 'boring' and a2.type == 'boring': 
...   return cmp(a1.value, a2.value) 
...  else: 
...   return cmp(a2.type, a1.type) 
... 
>>> for sm in sorted(stack, compare): 
...  print sm 
... 
<SortMe fancy 15> 
<SortMe fancy 3> 
<SortMe fancy 1> 
<SortMe fancy 22> 
<SortMe fancy 17> 
<SortMe boring 1> 
<SortMe boring 3> 
<SortMe boring 5> 
<SortMe boring 22>