Python列表排序：深入探讨sort()和sorted()_python sort 时间复杂度

更多Python学习内容：ipengtao.com

大家好，我是彭涛，今天为大家分享 Python列表排序：深入探讨sort()和sorted()，全文4700字，阅读大约15分钟。

在Python中，列表排序是一项常见而重要的任务。本文将深入研究列表排序的两种主要方法：sort() 方法和 sorted() 函数。通过详细的解释和丰富的示例代码，将全面探讨如何灵活、高效地利用这两种方式进行列表排序。

sort() 方法的基本用法

sort() 方法是列表对象的一个内置方法，能够直接对原始列表进行排序。

以下是一个基本的用法示例：

numbers = [4, 1, 7, 3, 9, 2]
numbers.sort()
print(numbers)  # 输出：[1, 2, 3, 4, 7, 9]

sort() 方法默认按升序排序，同时也支持降序排序：

numbers = [4, 1, 7, 3, 9, 2]
numbers.sort(reverse=True)
print(numbers)  # 输出：[9, 7, 4, 3, 2, 1]

sort() 方法的高级用法

1 自定义排序关键字

sort() 方法还允许通过关键字参数 key 指定一个自定义的排序函数。

以下是一个按字符串长度排序的示例：

words = ["apple", "banana", "orange", "kiwi"]
words.sort(key=len)
print(words)  # 输出：['kiwi', 'apple', 'banana', 'orange']

2 使用lambda函数

通过 lambda 函数，可以更灵活地定义排序规则。例如，按单词的最后一个字母进行排序：

words = ["apple", "banana", "orange", "kiwi"]
words.sort(key=lambda x: x[-1])
print(words)  # 输出：['banana', 'kiwi', 'apple', 'orange']

sorted() 函数的基本用法

与 sort() 方法不同，sorted() 函数不会修改原始列表，而是返回一个新的已排序列表。

以下是 sorted() 函数的基本用法：

numbers = [4, 1, 7, 3, 9, 2]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # 输出：[1, 2, 3, 4, 7, 9]
print(numbers)         # 输出：[4, 1, 7, 3, 9, 2]（原列表未改变）

sorted() 函数的高级用法

1 反向排序

与 sort() 方法类似，sorted() 函数也支持 reverse 参数，用于进行降序排序：

numbers = [4, 1, 7, 3, 9, 2]
sorted_numbers_desc = sorted(numbers, reverse=True)
print(sorted_numbers_desc)  # 输出：[9, 7, 4, 3, 2, 1]

2 自定义排序函数

利用 key 参数，可以实现与 sort() 方法相似的自定义排序：

words = ["apple", "banana", "orange", "kiwi"]
sorted_words = sorted(words, key=len)
print(sorted_words)  # 输出：['kiwi', 'apple', 'banana', 'orange']

3 使用 operator 模块

operator 模块提供了一些方便的函数，可用于更复杂的排序操作。

例如，按元组的第二个元素进行排序：

import operator
 
data = [(1, 5), (3, 2), (7, 8), (4, 1)]
sorted_data = sorted(data, key=operator.itemgetter(1))
print(sorted_data)  # 输出：[(4, 1), (3, 2), (1, 5), (7, 8)]

性能比较和选择

性能比较在选择使用 sort() 方法还是 sorted() 函数时至关重要。理解它们的性能特征有助于在不同场景中做出明智的选择。

sort() 方法的性能：

sort() 方法是一个原地排序方法，直接修改原始列表，因此在内存使用方面更为高效。它采用Timsort算法，结合了归并排序和插入排序的优点，对于大型数据集，sort() 方法通常表现得更出色。这是因为它避免了创建新的数据结构，直接在原有列表上进行排序操作，节省了额外的内存开销。

numbers = [4, 1, 7, 3, 9, 2]
numbers.sort()

sorted() 函数的性能：

sorted() 函数创建一个新的已排序列表，不修改原始列表，因此在某些情况下更安全。但是，由于它需要额外的内存来存储新的列表，对于大型数据集可能会引起内存开销较大的问题。特别是当原始数据集很大时，sorted() 可能不如 sort() 方法效率高。

numbers = [4, 1, 7, 3, 9, 2]
sorted_numbers = sorted(numbers)

如何选择：

1. 数据集大小： 对于大型数据集，尤其是内存有限的情况下，推荐使用 sort() 方法以降低内存压力。

2. 原始数据保留： 如果需要保留原始数据的顺序，或者避免直接修改原始数据，可以选择使用 sorted() 函数。

3. 性能需求： 如果性能是首要考虑因素，且没有保留原始数据的需求，那么 sort() 方法通常是更好的选择。

4. 稳定性： 由于 sort() 方法是原地排序，它在某些情况下可能不够稳定。如果稳定性对任务至关重要，可以考虑使用 sorted() 函数。

在实际应用中，根据任务需求综合考虑这些因素，选择适合的排序方式，以便在保证性能的同时满足其他需求。

探索稳定性和复杂对象排序

1 稳定性

在排序时，稳定性是一个重要的概念。稳定排序意味着如果有两个元素相等，排序后它们的相对顺序不会改变。Python的 sorted() 函数是稳定的，而 sort() 方法通常也是稳定的。

data = [(1, 2), (3, 2), (1, 1), (3, 1)]
sorted_data = sorted(data, key=lambda x: x[0])
print(sorted_data)  # 输出：[(1, 2), (1, 1), (3, 2), (3, 1)]（维持相对顺序）

2 对象排序

当处理复杂对象时，可以通过定义对象的 __lt__（小于）、__le__（小于等于）等特殊方法，使对象具有可比性，从而能够进行排序。

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
 
    def __lt__(self, other):
        return self.age < other.age
 
people = [Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)]
sorted_people = sorted(people)
print([person.name for person in sorted_people])  # 输出：['Bob', 'Alice', 'Charlie']

时间和空间复杂度分析

在排序算法的选择中，不仅要考虑性能，还需要了解排序算法的时间和空间复杂度，以便在不同的应用场景中做出明智的决策。

sort() 方法的时间和空间复杂度：

• 时间复杂度： sort() 方法采用Timsort算法，它的平均时间复杂度为O(n log n)，在最坏情况下为O(n log n)。这使得 sort() 在处理大型数据集时能够以较高的效率运行。

• 空间复杂度： sort() 方法是一个原地排序算法，它不需要额外的空间用于存储数据的副本，因此空间复杂度为O(1)。这使得它在内存使用方面更为高效。

sorted() 函数的时间和空间复杂度：

• 时间复杂度： sorted() 函数使用归并排序，其平均和最坏情况下的时间复杂度均为O(n log n)。尽管与 sort() 方法相当，但由于它创建了一个新的已排序列表，因此在常数因子上可能略逊一筹。

• 空间复杂度： sorted() 函数创建了一个新的列表，其空间复杂度为O(n)。相对于 sort() 方法的原地排序，sorted() 的空间复杂度略高，需要额外的内存存储新的列表。

如何选择：

1. 数据集大小： 对于小型数据集，两者的性能差异可能不明显。但对于大型数据集，由于 sort() 方法的原地排序和较低的空间复杂度，通常更为适用。

2. 原始数据保留： 如果需要保留原始数据的顺序，或者避免直接修改原始数据，可以选择使用 sorted() 函数。

3. 内存限制： 如果内存资源受限，sort() 方法的较低空间复杂度可能是一个优势。

4. 稳定性： 由于两者的时间复杂度相当，如果需要稳定性，可以优先选择 sorted() 函数。

最佳实践

在使用 sort() 方法和 sorted() 函数时，最佳实践涉及到代码的可读性、维护性以及对任务需求的灵活应对。以下是一些建议和最佳实践，有助于编写清晰、高效的排序代码。

1. 选择合适的排序方式

• 小型数据集： 对于小型数据集，两者的性能差异可能微乎其微。选择更符合你代码风格的方式，或者根据任务需求进行选择。

• 大型数据集： 对于大型数据集，考虑使用 sort() 方法，因为它是原地排序，不需要额外的内存，可能更为高效。

2. 利用key参数进行自定义排序

根据元素的某一属性排序： 使用 key 参数，通过元素的某一属性进行排序，例如按照字符串长度或对象的特定属性。

words = ["apple", "banana", "orange", "kiwi"]
words.sort(key=len)

使用lambda函数： 对于简单的排序规则，可以使用 lambda 函数来定义一个临时的排序函数。

words = ["apple", "banana", "orange", "kiwi"]
words.sort(key=lambda x: x[-1])

3. 考虑稳定性

• 需要保留相对顺序： 如果需要保留相等元素的相对顺序，考虑选择 sorted() 函数，因为它是稳定的。

4. 注重代码可读性

• 避免过于复杂的排序规则： 尽量保持排序规则的简洁和可读性，避免过于复杂的逻辑。

• 合理命名： 使用清晰的变量名和函数名，让代码更易读懂。

5. 实践异常处理

处理异常： 在实际应用中，始终考虑潜在的错误。合理使用异常处理机制，处理可能出现的问题。

try:
  numbers.sort()
except Exception as e:
  print(f"An unexpected error occurred: {e}")

通过综合考虑这些最佳实践，将能够更好地运用 sort() 方法和 sorted() 函数，确保代码既高效又易于维护。最终，选择更符合任务需求和代码风格的排序方式，有助于提高代码的可读性和可维护性。

总结

在本文中，深入探讨了Python中列表排序的两种主要方法：sort() 方法和 sorted() 函数。通过详细解释和丰富的示例代码，全面探讨了如何高效、灵活地利用这两种方式进行列表排序。

首先，学习了 sort() 方法，它是列表对象的原地排序方法。通过默认的升序排序和降序排序，以及高级用法如自定义排序关键字和lambda函数，理解了如何灵活运用 sort() 方法。其次，介绍了 sorted() 函数，它创建一个新的已排序列表而不修改原始列表。通过对比 sort() 方法，我们探讨了 sorted() 的优势，尤其是在需要保留原始数据顺序时。

深入研究了性能比较和选择的因素，考虑了在不同场景中选择 sort() 或 sorted() 的合适性。在此基础上，进行了时间和空间复杂度的分析，了解了它们在实际应用中的性能表现。最后，总结了最佳实践，强调了代码可读性、自定义排序规则的灵活运用、异常处理的实践等关键方面。这些最佳实践有助于编写清晰、高效、易于维护的排序代码。通过深入学习这些内容，读不仅能够熟练运用 sort() 方法和 sorted() 函数，还能够根据具体需求和场景选择最适合的排序方式。

如果你觉得文章还不错，请大家 点赞、分享、留言 下，因为这将是我持续输出更多优质文章的最强动力！

更多Python学习内容：ipengtao.com

干货笔记整理

  100个爬虫常见问题.pdf ，太全了！

Python 自动化运维 100个常见问题.pdf

Python Web 开发常见的100个问题.pdf

124个Python案例，完整源代码！

PYTHON 3.10中文版官方文档

耗时三个月整理的《Python之路2.0.pdf》开放下载

最经典的编程教材《Think Python》开源中文版.PDF下载

点击“阅读原文”，获取更多学习内容