[ Python 文章收集 ] Sorting Mini-HOW TO

來源自 這裡 
Preface : 
Python lists 有內建的 sort() 函數提供 in-place 的排序 ; 另外在 Python 內建函數也有提供 sorted() API 可以提供用來排序現有的 list (但不改變它), 並建立一個新的 sorted list. 底下將對這兩種 sorting 的使用方法進行說明與介紹. 

Sorting Basics : 
一個簡單的使用範例, 你可以如下使用 sorted() 函數, 它會返回一個全新的 sorted list : 

>>> orig_list = [5, 2, 3, 1, 4]
>>> sort_list = sorted(orig_list)
>>> orig_list
[5, 2, 3, 1, 4] # sorting 後, 原先的 list 不會改變
>>> sort_list
[1, 2, 3, 4, 5]

或者你可以直接呼叫 list.sort() 來進行排序, 它會修改呼叫方法上的 list 並返回 None. 通常它會比使用 sorted() 函數有效率一點, 前提是你預期原先的 list 可能被改變並成為 sorting 後的結果: 

>>> orig_list
[5, 2, 3, 1, 4]
>>> orig_list.sort() # 返回 None
>>> orig_list
[1, 2, 3, 4, 5]

但就應用面來說, sorted() 遠比 list.sort() 強大, 因為只要是 iterable ( A container is said to be iterable if it has the __iter__ method defined.) 的物件它都能處理. 

Key Functions : 
在 Python 2.4 之後, list.sort() 與 sorted() 都支援參數 key 來指定一個函數, 在進行 sorting 前對該 element 進行前置處理. 底下為一個簡單範例, 我們希望在排序時能夠忽略大小寫的差別 (case-insensitive string comparison), 因此在進行排序前我們會利用 key 將比較的 element 統一轉成小寫 : 

>>> sorted("This is a test staring from Alice".split(), key=str.lower)
['a', 'Alice', 'from', 'is', 'staring', 'test', 'This']
>>> sorted("This is a test staring from Alice".split()) # 如果沒有忽略大小寫, 大寫會排到小寫前面.
['Alice', 'This', 'a', 'from', 'is', 'staring', 'test']

事實上 key 的用法不僅於此, 在你的 sorting data 的 element 是由 tuple 組成時, 你可以使用它決定是用 tuple 中的某一個元素進行排序. 例如下面範例 sorting 的 tuple 共有三個元素, 而透過 key我們取出最後一個來進行 sorting : 

>>> student_tuples = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

如果你的 sorting data 是類別的話, 而你想要對該類別的某個 attribute 進行 sorting 也是同樣的方法 : 
 

Operator Module Functions : 
上面示範的用法因為非常常見, 故現有的 operator module 在 Python 2.6 之後提供了itemgetter(), attrgetter() 函數省掉了你需要自己撰寫類似的代碼, 因此上面的範例代碼可以用下面更簡潔更快的方法完成 sorting : 

>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

甚至你也可以指定 multiple level 的 sorting (同時對兩個元素或是屬性進行 sorting): 

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

Ascending and Descending : 
在 list.sort() 與 sorted() 都支援參數 reverse 讓你可以決定是降序(True)還是升序排列(False, 預設值) : 

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Sort Stability and Complex Sorts : 
從 Python 2.2 之後, sorting 保證是 stable. 意味如果多筆 record sorting 結果一樣, 則在原始未 sorting 前的位置順序會被保留 : 

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

(Notice how the two records for 'blue' retain their original order so that ('blue', 1) is guaranteed to precede ('blue', 2).) 

而這樣的特性讓你可以同時呼叫 sorted 多次 (對不同的元素或是屬性) 來進行所謂的 Complex sorts. 例如下面的範例先對 "age" 升序排序 ; 再對 "grade" 降序排列 : 

>>> student_objects
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> s = sorted(student_objects, key=attrgetter('age'))
>>> s
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(s, key=attrgetter('grade'), reverse=True)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

(The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.) 

The Old Way Using the cmp Parameter : 
在 Py2.x 的 sorted() 函數你可以使用參數 cmp 來決定自己的 compare 方式. 該函數會傳入兩個比較值(x,y), 並返回數值 : 返回負數代表 x 小於 y; 返回 0 代表 x 等於 y; 返回正值代表 x 大於 y. 底下為簡單使用範例 : 
 

非常直覺的是如果你要 reverse 上面的 sorting 結果, 只要替換 x,y 的位置 : 
 

然而這個參數在 Py3.0 被移除了, 因此如果你要將 Py2.x 的代碼轉移到 Py3.0 以後的版本, 可以將你自定義的 compare 函數透過下面的 cmp_to_key 函數做包裝, 並指定給 key 參數 : 

view plaincopy to clipboardprint?

1. def cmp_to_key(mycmp):  
2.     'Convert a cmp= function into a key= function'  
3.     class K(object):  
4.         def __init__(self, obj, *args):  
5.             self.obj = obj  
6.         def __lt__(self, other):  
7.             return mycmp(self.obj, other.obj) < 0  
8.         def __gt__(self, other):  
9.             return mycmp(self.obj, other.obj) > 0  
10.         def __eq__(self, other):  
11.             return mycmp(self.obj, other.obj) == 0  
12.         def __le__(self, other):  
13.             return mycmp(self.obj, other.obj) <= 0  
14.         def __ge__(self, other):  
15.             return mycmp(self.obj, other.obj) >= 0  
16.         def __ne__(self, other):  
17.             return mycmp(self.obj, other.obj) != 0  
18.     return K  

如此你就可以在 Py3.0 後繼續使用你自定義的 compare 函數, 在 Python 2.7 之後, cmp_to_key() 定義在模組 functools 中 : 
 

Supplement : 
* Understanding Python iterable and iterator