排序技術¶

作者:: Andrew Dalke 和 Raymond Hettinger

Python 列表有一個內建的 list.sort() 方法，它會原地修改列表。還有一個 sorted() 內建函式，它從可迭代物件構建一個新的排序列表。

在本文件中，我們將探討使用 Python 排序資料的各種技術。

排序基礎¶

簡單的升序排序非常容易：只需呼叫 sorted() 函式。它返回一個新的排序列表

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

你也可以使用 list.sort() 方法。它會原地修改列表（並返回 None 以避免混淆）。通常，它不如 sorted() 方便，但如果你不需要原始列表，它會稍微高效一些。

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

另一個區別是 list.sort() 方法僅為列表定義。相比之下， sorted() 函式接受任何可迭代物件。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

鍵函式¶

list.sort() 和 sorted() 都有一個 key 引數，用於指定在進行比較之前對每個列表元素呼叫的函式（或其他可呼叫物件）。

例如，這是一個不區分大小寫的字串比較

>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key 引數的值應該是一個函式（或其他可呼叫物件），它接受單個引數並返回一個用於排序的鍵。這種技術速度很快，因為鍵函式對於每個輸入記錄只調用一次。

一種常見的模式是使用物件的一些索引作為鍵來排序複雜物件。例如

>>> 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)]

相同的技術適用於具有命名屬性的物件。例如

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

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

具有命名屬性的物件可以透過如上所示的常規類建立，也可以是 dataclass 或命名元組的例項。

operator 模組函式和偏函式求值¶

上面顯示的鍵函式模式非常常見，因此 Python 提供了方便的函式，使訪問器函式更簡單和更快。operator 模組具有 itemgetter()、attrgetter() 和 methodcaller() 函式。

使用這些函式，上面的示例變得更簡單和更快

>>> 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)]

operator 模組函式允許多級排序。例如，要先按 grade 然後按 age 排序

>>> 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)]

functools 模組為建立鍵函式提供了另一個有用的工具。partial() 函式可以減少多引數函式的 arity，使其適合用作鍵函式。

>>> from functools import partial
>>> from unicodedata import normalize

>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

升序和降序¶

list.sort() 和 sorted() 都接受一個具有布林值的 reverse 引數。這用於標記降序排序。例如，要獲取反向 age 順序的學生資料

>>> 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)]

排序穩定性和複雜排序¶

排序保證是穩定的。這意味著當多個記錄具有相同的鍵時，它們的原始順序會被保留。

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

請注意，blue 的兩個記錄如何保留其原始順序，因此保證 ('blue', 1) 在 ('blue', 2) 之前。

這個出色的屬性使你可以在一系列排序步驟中構建複雜的排序。例如，要按降序 grade 然後按升序 age 排序學生資料，請先執行 age 排序，然後再次使用 grade 排序

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

這可以抽象到一個包裝函式中，該函式可以接收列表和欄位和順序的元組，以便在多個傳遞中進行排序。

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Python 中使用的 Timsort 演算法可以高效地執行多個排序，因為它能夠利用資料集中已經存在的任何排序。

裝飾-排序-去裝飾¶

這個習慣用法在三個步驟之後被稱為裝飾-排序-去裝飾

首先，初始列表使用控制排序順序的新值進行裝飾。
其次，對裝飾列表進行排序。
最後，刪除裝飾，建立一個僅包含新順序的初始值的列表。

例如，要使用 DSU 方法按 grade 排序學生資料

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

這個習慣用法之所以有效，是因為元組是按字典順序比較的；比較第一項；如果它們相同，則比較第二項，依此類推。

在裝飾列表中，並非在所有情況下都必須包含索引 i ，但包含它有兩個好處

排序是穩定的 - 如果兩項具有相同的鍵，則它們的順序將在排序後的列表中保留。
原始項不必是可比較的，因為裝飾元組的排序將最多由前兩項確定。因此，例如，原始列表可能包含無法直接排序的複數。

此習慣用法的另一個名稱是 Schwartzian transform，以 Randal L. Schwartz 的名字命名，他在 Perl 程式設計師中推廣了它。

現在 Python 排序提供了鍵函式，因此通常不需要此技術。

比較函式¶

與返回排序的絕對值的鍵函式不同，比較函式計算兩個輸入的相對順序。

例如，天平比較兩個樣本，給出相對順序：較輕、相等或較重。同樣，比較函式（例如 cmp(a, b)）對於小於返回負值，如果輸入相等則返回零，對於大於則返回正值。

從其他語言轉換演算法時，經常會遇到比較函式。此外，某些庫提供比較函式作為其 API 的一部分。例如，locale.strcoll() 是一個比較函式。

為了適應這些情況，Python 提供了 functools.cmp_to_key 來包裝比較函式，使其可用作鍵函式

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

雜項¶

對於區域設定感知排序，請使用 locale.strxfrm() 作為鍵函式，或使用 locale.strcoll() 作為比較函式。這是必要的，因為即使底層字母表相同，“字母”排序也可能因文化而異。

reverse 引數仍然保持排序穩定性（以便具有相同鍵的記錄保持原始順序）。有趣的是，可以透過兩次使用內建的 reversed() 函式來模擬該效果，而無需使用引數

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> assert standard_way == double_reversed
>>> standard_way
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]

在比較兩個物件時，排序例程使用 <。因此，透過定義 __lt__() 方法，很容易向類新增標準排序順序
```
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
```
但是請注意，如果 __lt__() 沒有實現，< 可以回退使用 __gt__() （有關機制的詳細資訊，請參閱 object.__lt__()）。為避免意外，PEP 8 建議實現所有六個比較方法。提供了 total_ordering() 裝飾器來簡化這項任務。
鍵函式不必直接依賴於正在排序的物件。鍵函式也可以訪問外部資源。例如，如果學生成績儲存在字典中，它們可以用來排序單獨的學生姓名列表。
```
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
```

部分排序¶

有些應用程式只需要對部分資料進行排序。標準庫提供了一些比完整排序工作量更少的工具。

min() 和 max() 分別返回最小值和最大值。這些函式對輸入資料進行單次遍歷，幾乎不需要輔助記憶體。
heapq.nsmallest() 和 heapq.nlargest() 分別返回 n 個最小和最大的值。這些函式對資料進行單次遍歷，每次只在記憶體中保留 n 個元素。對於相對於輸入數量較小的 n 值，這些函式進行的比較次數比完整排序要少得多。
heapq.heappush() 和 heapq.heappop() 建立並維護資料的部分排序排列，將最小的元素保持在位置 0。這些函式適用於實現優先順序佇列，優先順序佇列通常用於任務排程。