萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 列表 sort() 方法完全指南:原地排序、key 函數、reverse、穩定性與 Timsort 算法

list.sort() 是 Python 列表原地排序的核心方法,基於 Timsort 混合排序算法 (歸併 + 插入),具有 O(n log n) 最壞情況、O(n) 最佳情況 (近有序)、穩定排序等優異特性。本文全面解析參數、鍵函數、效能與進階技巧。

基本語法


lst.sort(key=None, reverse=False)
  • key:函數,提取比較鍵,每元素調用一次 (Schwartzian transform)
  • reverse:True 降序,False 升序 (默認)
  • 返回: None (原地修改)
  • 異常: TypeError (元素不可比較,如 1 < 'a')

基礎用法


numbers = [3, 1, 4, 1, 5, 9]
numbers.sort()
print(numbers)  # [1, 1, 3, 4, 5, 9]

numbers.sort(reverse=True)
print(numbers)  # [9, 5, 4, 3, 1, 1]

key 函數:自定義排序邏輯核心

1. 按屬性/鍵排序對象


class Student:
    def __init__(self, name, score):
        self.name, self.score = name, score
    def __repr__(self): return f"{self.name}({self.score})"

students = [Student('Bob', 85), Student('Alice', 92), Student('Charlie', 78)]
students.sort(key=lambda s: s.score)      # 按分數升序
students.sort(key=lambda s: s.score, reverse=True)  # 降序
students.sort(key=lambda s: s.name)       # 按姓名字母序

2. 多鍵排序 (元組鍵)


data = [('b', 2), ('a', 3), ('a', 1), ('b', 1)]
# 先按字母升序,再按數字降序
data.sort(key=lambda x: (x[0], -x[1]))
# [('a', 3), ('a', 1), ('b', 2), ('b', 1)]

3. operator 模組加速


from operator import attrgetter, itemgetter

# 屬性訪問
students.sort(key=attrgetter('score'))

# 索引/鍵訪問
data.sort(key=itemgetter(1, 0))  # 先第2項,再第1項

4. 複雜邏輯:鍵函數返回元組


# 按長度排序,長度相同按字母序
words = ['apple', 'pie', 'banana', 'pear', 'kiwi']
words.sort(key=lambda w: (len(w), w))
# ['pie', 'kiwi', 'pear', 'apple', 'banana']

穩定排序特性 (關鍵優勢)


# 相等鍵元素保持原相對順序
data = [('a', 1), ('b', 1), ('a', 2)]
data.sort(key=lambda x: x[1])
# [('a', 1), ('b', 1), ('a', 2)]  # ('a',1) 仍在 ('b',1) 前

# 多次排序實現多鍵 (利用穩定性)
data.sort(key=lambda x: x[0])  # 先按字母
data.sort(key=lambda x: x[1])  # 再按數字 → 字母序作為次要鍵保留

效能特性 (Timsort)

情況時間複雜度說明
隨機數據O(n log n)標準情況
已排序/逆序/近有序O(n)Timsort 利用自然連續段
部分有序O(n + k log k)k 為無序段數量

import timeit, random

# 已排序列表極快
setup = 'lst = list(range(10000))'
timeit.timeit('lst.sort()', setup=setup, number=100)  # ~0.02s

# 隨機列表
setup = 'import random; lst = [random.random() for _ in range(10000)]'
timeit.timeit('lst.sort()', setup=setup, number=100)  # ~0.15s

sorted() vs sort()

特性list.sort()sorted(iterable)
原地修改✅❌ (返回新列表)
返回值None新排序列表
輸入類型僅列表任意可迭代對象
記憶體O(1) 額外O(n)

進階技巧

1. 自定義類支援排序


from functools import total_ordering

@total_ordering
class Version:
    def __init__(self, s):
        self.parts = tuple(map(int, s.split('.')))
    def __eq__(self, other): return self.parts == other.parts
    def __lt__(self, other): return self.parts < other.parts

versions = [Version('1.10'), Version('1.2'), Version('2.0')]
versions.sort()
print([v.parts for v in versions])  # [(1,2), (1,10), (2,0)]

2. 區域敏感排序 (locale)


import locale
locale.setlocale(locale.LC_COLLATE, 'zh_CN.UTF-8')
names = ['张三', '李四', '王五']
names.sort(key=locale.strxfrm)  # 按拼音/筆畫排序

3. 降序鍵函數技巧


# 數值取負
lst.sort(key=lambda x: -x.score)

# 字符串反轉 (非直觀)
lst.sort(key=lambda s: s[::-1])  # 按反序排序

常見陷阱

  • 異構類型比較: Python 3 禁止 1 < 'a' → TypeError,需統一類型或 key 函數處理
  • 鍵函數副作用: key 應為純函數,避免修改外部狀態
  • 大數據集記憶體: sort() 原地操作省記憶體,sorted() 需額外 O(n)
  • 自定義 __lt__ 陷阱: 僅定義 __lt__ 時用 @total_ordering 補全

總結

  • sort(key=..., reverse=...) 是靈活強大的原地排序
  • key 函數是自定義邏輯的核心,善用 attrgetter/itemgetter/元組
  • Timsort 穩定、適應性強,近有序數據極快
  • 需新列表用 sorted(),原地用 sort()

掌握 sort() 的全部能力,能讓你用最簡潔代碼表達複雜排序邏輯,並充分發揮 Python 排序引擎的高效能優勢。

copyright © 萬盛學電腦網 all rights reserved