当前位置：首页 > 文章列表 > 文章 > python教程 > Python排序方法全解析

Python排序方法全解析

2025-07-17 13:37:41 0浏览收藏

golang学习网今天将给大家带来《Python排序方法与算法详解》，感兴趣的朋友请继续看下去吧！以下内容将会涉及到等等知识点，如果你是正在学习文章或者已经是大佬级别了，都非常欢迎也希望大家都能给我建议评论哈~希望能帮助到大家！

Python中实现排序主要依赖内置的list.sort()方法和sorted()函数，它们底层基于高效的Timsort算法，同时也可以手动实现冒泡、快速、归并等经典排序算法。1. list.sort()方法直接在原列表上排序，不返回新列表；2. sorted()函数接受任何可迭代对象并返回新排序列表，原始数据不变；3. 二者均支持key参数和reverse参数，实现自定义排序逻辑；4. Timsort结合归并排序和插入排序优点，具备稳定性、高效性和适应性；5. 内置排序性能远优于手动实现，适用于绝大多数实际场景；6. 对复杂数据或自定义对象排序时，可使用lambda表达式或operator模块的attrgetter/itemgetter；7. 处理大数据量时，需关注内存、CPU及I/O瓶颈，优化策略包括简化key函数、预计算、分块处理、使用heapq等部分排序方法。

Python如何实现排序？算法与内置方法

Python中实现排序主要依赖其内置的list.sort()方法和sorted()函数，它们底层都基于高效的Timsort算法。此外，为了理解算法原理或应对特定场景，我们也可以手动实现如冒泡、快速、归并等经典排序算法。

解决方案

Python在处理数据排序时，提供了非常便捷且性能优异的内置工具，同时也不排斥我们自己动手实现那些经典的排序算法，毕竟理解原理有时候比直接使用更重要。

内置排序方法与函数：

list.sort() 方法： 这是列表（list）对象自带的方法，它会直接在原地修改列表，不会返回新的列表。这意味着原有的数据顺序会被覆盖。

my_list = [3, 1, 4, 1, 5, 9, 2, 6]
my_list.sort() # 原地排序
print(my_list) # 输出: [1, 1, 2, 3, 4, 5, 6, 9]

# 降序排序
my_list.sort(reverse=True)
print(my_list) # 输出: [9, 6, 5, 4, 3, 2, 1, 1]

sorted() 函数： 这是一个内置函数，它可以接受任何可迭代对象（如列表、元组、字符串、字典的键等），并返回一个新的、已排序的列表。原始的可迭代对象不会被修改。

my_tuple = (3, 1, 4, 1, 5)
sorted_list = sorted(my_tuple)
print(sorted_list) # 输出: [1, 1, 3, 4, 5]
print(my_tuple)    # 输出: (3, 1, 4, 1, 5) - 原始元组不变

my_string = "python"
sorted_chars = sorted(my_string)
print(sorted_chars) # 输出: ['h', 'n', 'o', 'p', 't', 'y']

# 结合 key 参数进行自定义排序
words = ["banana", "apple", "cherry", "date"]
# 按字符串长度排序
sorted_by_length = sorted(words, key=len)
print(sorted_by_length) # 输出: ['date', 'apple', 'banana', 'cherry']

# 结合 lambda 表达式和 reverse
data = [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]
sorted_by_age_desc = sorted(data, key=lambda x: x["age"], reverse=True)
print(sorted_by_age_desc) # 输出: [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}]

这两个内置功能在底层都使用了Timsort算法，它是一种混合排序算法，结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的优点，在实际数据中表现非常高效。

手动实现排序算法（示例）：

虽然内置方法足够强大，但理解算法原理是另一回事。这里简单展示几个经典算法的Python实现：

冒泡排序 (Bubble Sort)： 简单直观，但效率较低，尤其不适合大数据量。它通过重复遍历列表，比较相邻元素并交换位置，直到没有元素需要交换。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: # 如果一趟下来没有交换，说明已经有序
            break
    return arr
# print(bubble_sort([64, 34, 25, 12, 22, 11, 90])) # 输出: [11, 12, 22, 25, 34, 64, 90]

快速排序 (Quick Sort)： 通常情况下性能优异，是一种分治算法。它选择一个“基准”（pivot）元素，将数组分成两部分：小于基准的和大于基准的，然后递归地对这两部分进行排序。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
# print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # 输出: [1, 1, 2, 3, 6, 8, 10]

归并排序 (Merge Sort)： 也是一种分治算法，稳定且性能稳定（O(n log n)）。它将列表递归地分成两半，直到每个子列表只有一个元素，然后将这些子列表合并（merge）成一个有序的列表。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    return merge(left_sorted, right_sorted)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
# print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # 输出: [3, 9, 10, 27, 38, 43, 82]

Python内置排序机制的工作原理是什么？它比手动实现算法更优吗？

Python内置的sort()方法和sorted()函数都采用了名为Timsort的混合排序算法。Timsort是一个非常聪明的设计，它结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的优点。它的核心思想是：对于小块数据（通常是几十个元素），插入排序非常高效；而对于大块数据，归并排序的O(n log n)复杂度则更有优势。

具体来说，Timsort会先将输入数据分解成一系列“自然有序的”或“部分有序的”子序列（称为runs）。如果某个run的长度小于预设的最小长度（通常是32或64），它会使用插入排序将其扩展到最小长度并使其有序。接着，Timsort会使用归并排序的思想，将这些有序的runs合并起来，直到所有数据都合并成一个完整的有序序列。

Timsort的优势在于：

稳定性： 对于相等元素的排序，Timsort能保持它们在原始输入中的相对顺序，这在处理复杂数据结构时非常有用。
高效性： 平均和最坏情况下的时间复杂度都是O(n log n)。
适应性： 它能识别并利用数据中已存在的有序性，对于部分有序的数据，它的性能会非常接近O(n)。
内存优化： 归并排序通常需要额外的O(n)空间，Timsort通过巧妙的策略，将辅助空间需求降到了O(n/2)甚至更低，在某些情况下可以做到O(1)的额外空间。

它比手动实现算法更优吗？

绝大多数情况下，是的，Timsort比我们手动实现的任何经典排序算法都要优越。

我个人觉得，如果你不是在研究算法本身，或者有极其特殊的需求，直接用内置的就对了，省心又高效。原因有几点：

C语言实现： Python的Timsort是用C语言实现的，这意味着它的执行速度远超纯Python代码。Python解释器本身的开销，使得纯Python实现的算法在性能上很难与C语言相匹敌。
高度优化： Timsort的实现经过了多年的优化和测试，考虑了各种边缘情况和数据分布，包括内存访问模式、缓存利用率等，这些细节在普通的算法实现中很难兼顾。
通用性： 它能优雅地处理各种数据类型，包括数字、字符串、自定义对象，并且可以通过key参数轻松实现复杂排序逻辑。
稳定性： 对于许多应用场景，排序的稳定性是必要的，而Timsort天然支持。

所以，除非你真的在做算法性能对比实验，或者有非常奇特的、Timsort无法满足的特定需求（这种情况极其罕见），否则，直接使用list.sort()和sorted()是最佳选择。自己实现算法更多是为了学习和理解，而不是为了生产环境的性能。

如何根据复杂条件或自定义对象属性进行排序？

在实际开发中，我们很少会遇到只对数字或字符串进行简单升序排列的需求。更多时候，我们需要根据对象的某个特定属性、多个属性的组合、或者通过一个自定义的计算逻辑来决定排序顺序。Python的key参数就是为此而生，它允许你指定一个函数，这个函数会在排序前应用于列表中的每个元素，并返回一个用于比较的值。

这块功能是真的强大，我以前刚接触的时候，觉得能把对象按各种奇奇怪怪的规则排好序，简直是魔法。尤其是处理一些业务数据时，简直是救星。

使用 key 参数和 lambda 表达式：

key参数接受一个函数，这个函数会作用于列表中的每一个元素，并返回一个用于比较的值。lambda表达式在这里非常常用，因为它提供了一种简洁的方式来定义匿名函数。

按字符串长度排序：

words = ["apple", "banana", "kiwi", "grapefruit"]
# 按单词长度升序
sorted_by_len = sorted(words, key=len)
print(sorted_by_len) # 输出: ['kiwi', 'apple', 'banana', 'grapefruit']

按字典中某个键的值排序：

students = [
    {"name": "Alice", "age": 20, "score": 85},
    {"name": "Bob", "age": 22, "score": 90},
    {"name": "Charlie", "age": 20, "score": 78}
]
# 按分数降序排序
sorted_by_score = sorted(students, key=lambda s: s["score"], reverse=True)
print(sorted_by_score)
# 输出: [{'name': 'Bob', 'age': 22, 'score': 90}, {'name': 'Alice', 'age': 20, 'score': 85}, {'name': 'Charlie', 'age': 20, 'score': 78}]

# 先按年龄升序，年龄相同则按分数降序
sorted_multi_criteria = sorted(students, key=lambda s: (s["age"], -s["score"]))
print(sorted_multi_criteria)
# 输出: [{'name': 'Charlie', 'age': 20, 'score': 78}, {'name': 'Alice', 'age': 20, 'score': 85}, {'name': 'Bob', 'age': 22, 'score': 90}]
# 注意：-s["score"] 是为了实现降序，因为默认是升序。

使用 operator 模块的 attrgetter 和 itemgetter：

对于常见的按对象属性或字典键排序的场景，operator模块提供了更高效的函数：attrgetter和itemgetter。它们返回一个可调用的对象，比lambda表达式在性能上略有优势，尤其是在处理大量数据时。

按自定义对象属性排序：

from operator import attrgetter

class Product:
    def __init__(self, name, price, stock):
        self.name = name
        self.price = price
        self.stock = stock

    def __repr__(self): # 为了方便打印
        return f"Product({self.name}, ${self.price}, Stock:{self.stock})"

products = [
    Product("Laptop", 1200, 50),
    Product("Mouse", 25, 200),
    Product("Keyboard", 75, 100)
]

# 按价格升序
sorted_by_price = sorted(products, key=attrgetter("price"))
print(sorted_by_price)
# 输出: [Product(Mouse, $25, Stock:200), Product(Keyboard, $75, Stock:100), Product(Laptop, $1200, Stock:50)]

# 先按库存降序，库存相同则按价格升序
sorted_multi_attr = sorted(products, key=attrgetter("stock", "price"), reverse=True) # reverse=True 只对第一个元素生效
# 如果要实现 stock 降序，price 升序，需要更复杂的 key
sorted_multi_attr_custom = sorted(products, key=lambda p: (-p.stock, p.price))
print(sorted_multi_attr_custom)
# 输出: [Product(Mouse, $25, Stock:200), Product(Keyboard, $75, Stock:100), Product(Laptop, $1200, Stock:50)]

按字典键排序（等同于lambda x: x['key']）：

from operator import itemgetter

students = [
    {"name": "Alice", "age": 20, "score": 85},
    {"name": "Bob", "age": 22, "score": 90},
]
sorted_by_name = sorted(students, key=itemgetter("name"))
print(sorted_by_name)
# 输出: [{'name': 'Alice', 'age': 20, 'score': 85}, {'name': 'Bob', 'age': 22, 'score': 90}]

这些方法提供了极大的灵活性，让你可以根据几乎任何自定义逻辑来排序Python中的数据结构，无论是简单的元组、字典还是复杂的自定义对象。

在处理大量数据时，排序的性能瓶颈和优化策略有哪些？

处理大量数据时，排序可不是简单的 list.sort() 一句代码就能搞定的了。我记得有一次，一个几千万行的日志文件要按时间戳排序，直接加载内存就爆了，那会儿才意识到，排序这事儿，还真不是小打小闹。它可能会成为整个应用程序的性能瓶颈，尤其是在内存、CPU和I/O方面。

常见的性能瓶颈：

内存限制 (Memory Limits)：
- 数据量过大： 当数据量远超可用内存时，直接加载到内存中进行排序会导致MemoryError。即使不报错，频繁的内存交换（swapping）也会极大降低性能。
- 临时空间需求： 某些排序算法（如归并排序）需要额外的临时存储空间，即使是Timsort也需要一部分辅助空间。
CPU 密集型操作 (CPU-Intensive Operations)：
- 比较操作的开销： 排序的核心是元素的比较。如果key函数执行的逻辑非常复杂或耗时（例如，涉及数据库查询、网络请求、复杂的正则匹配等），那么即使是O(n log n)的算法，其常数因子也会变得非常大，导致整体速度变慢。
- 元素交换/移动： 尤其对于大型对象，每次交换或移动元素可能涉及大量内存拷贝，增加CPU负担。
I/O 瓶颈 (I/O Bottlenecks)：
- 数据读取/写入： 如果数据存储在磁盘上（如文件、数据库），那么从磁盘读取数据和将排序结果写回磁盘的I/O速度可能会成为主要瓶颈，而不是排序算法本身。

优化策略：

优化 key 函数： 这是最直接也最常见的优化点。确保key函数尽可能地快。
- 避免复杂计算： key函数应该只做最少的必要计算来提取比较值。
- 使用 operator.attrgetter 或 operator.itemgetter： 对于按属性或字典键排序，它们通常比lambda表达式更高效。
- 预计算： 如果key函数的计算成本很高，并且数据不会改变，可以考虑在排序前预先计算好所有元素的key值，然后创建一个包含(key_value, original_element)的元组列表，再对这个列表进行排序。
利用部分排序或近似排序：
- heapq.nlargest() / heapq.nsmallest()： 如果你只需要找到最大/最小的N个元素，而不需要对整个列表排序，heapq模块提供了非常高效的方法（时间复杂度O(N log K)，K为N个元素）。
```
import heapq
data = [1, 8, 2, 7, 3, 6, 4, 5]
# 找出最大的3个元素
largest_3 = heapq.nlargest(3, data) # [8, 7, 6]
```
- bisect 模块： 如果你需要在已排序的列表中插入元素并保持有序，或者查找某个元素的位置，bisect模块非常有用，避免了每次插入都重新排序整个列表。
分块处理 (Chunking) 或外部排序 (External Sorting)： 当数据量大到无法一次性加载到