[Python] About 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 啦。