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>