Python Idiom: sort

本文將介紹如何使用 sort()， 參考資料來自 Sorting Mini-HowTo， 首先介紹基本用法

data = [2, 3, 4, 5, 1]
data.sort()

上述程式碼會將 data 的元素由小到大排序， 因為 sort() 是直接排序 data 的元素，而不是排序複製 data 的元素， 所以傳回值是 None 以避免困擾，如果要將排序過的資料傳給另一個序列要使用 sorted()，如

sorted_data = sorted(data)

假設現在 data 改成如下

data = [(11, 5, 1000), (13, 4, 10),
        (17, 6, 100), (19, 5, 1) ]

想要以 tuple 的第二、三、一個元素的大小做排序，該怎麼做？ 熟悉 C 語言 qsort() 的人可能會想到 ^[1]

def my_cmp(x, y):
     return cmp((x[1], x[2], x[0]), (y[1], y[2], y[0]))
data.sort(cmp=my_cmp)

但 Python 2.4 之後提供了更好更快的做法

def my_key(item):
     return (item[1], item[2], item[0])
data.sort(key=my_key)

key 的使用方式比前面 cmp 的方式來的直覺， 而且速度較快，因為排序的時候，只要需要比較的動作就會呼叫 cmp， 而 key 只會被呼叫 n 次，n 是序列的長度，所以 key 的速度較快。 其實不用自己定義 my_key，利用 itemgetter 就可以達到想要的結果了

from operator import itemgetter
data.sort(key=itemgetter(1,2,0))

最後還有一個問題，如果要依字母排序，不分大小寫，該怎麼做？ 利用 str.lower 即可

words = "Poets often use many words".split()
words.sort(key=str.lower)

註：

1. Python 3.0 已經 淘汰 cmp() 了。
2. 在 Python 2.4 之前還沒有 key 可以使用， 可是如果用自定的函數來比大小速度又太慢， 於是就有了 Decorate-Sort-Undecorate (DSU) 這種利用內建 sort() 的聰明方法， 首先建立一個新的序列，這個序列的每一項是一個 tuple， tuple 的前面是 排序時根據的 key，而 tuple 的後面是原來序列中的項，這個動作就叫作 decorate (裝飾)， 之後對這個新的序列排序， 然後從排序過的新序列中抽出原來的序列，這個動作叫作 undecorate (反裝飾)， 全部的過程如下

   decorated_data = [(x[1], x[2], x[0], x) for x in data]
   decorated_data.sort()
   sorted_data = [y[-1] for y in decorated_data]
   

   這一招在 Perl 裡面叫做 Schwartzian transform。 不過現在既然有方便的 key 可以使用，就不用自己做 DSU 啦。