1. 排序算法概述
排序是计算机科学中最基础且重要的算法之一，它将一组数据按照特定顺序（升序或降序）重新排列。Python作为一门高级编程语言，提供了多种内置的排序方法，同时也支持各种经典排序算法的实现。
2. Python内置排序方法
2.1 list.sort()方法
list.sort()方法会直接修改原列表，默认按升序排序：
numbers = [3, 1, 4, 1, 5, 9, 2, 6] numbers.sort() print(numbers) # 输出：[1, 1, 2, 3, 4, 5, 6, 9]2.2 sorted()函数
sorted()函数返回一个新的排序列表，不修改原列表：
numbers = [3, 1, 4, 1, 5, 9, 2, 6] sorted_numbers = sorted(numbers) print(sorted_numbers) # 输出：[1, 1, 2, 3, 4, 5, 6, 9] print(numbers) # 输出：[3, 1, 4, 1, 5, 9, 2, 6]（原列表不变）2.3 自定义排序规则
通过key参数可以指定排序依据：
# 按字符串长度排序 words = ["apple", "banana", "cherry", "date"] words.sort(key=len) print(words) # 输出：['date', 'apple', 'banana', 'cherry'] 按元组第二个元素排序 pairs = [(1, 9), (2, 7), (3, 5), (4, 3)] pairs.sort(key=lambda x: x[1]) print(pairs) # 输出：[(4, 3), (3, 5), (2, 7), (1, 9)]2.4 降序排序
使用reverse=True参数进行降序排序：
numbers = [3, 1, 4, 1, 5, 9, 2, 6] numbers.sort(reverse=True) print(numbers) # 输出：[9, 6, 5, 4, 3, 2, 1, 1]3. 经典排序算法实现
3.1 冒泡排序（Bubble Sort）
冒泡排序通过重复遍历列表，比较相邻元素并交换位置来实现排序：
def bubble_sort(arr): n = len(arr) for i in range(n): # 最后i个元素已经排好序 for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr 测试 arr = [64, 34, 25, 12, 22, 11, 90] print("排序前:", arr) print("排序后:", bubble_sort(arr.copy()))时间复杂度：O(n²)
空间复杂度：O(1)
3.2 选择排序（Selection Sort）
选择排序每次从未排序部分选择最小（或最大）元素放到已排序部分的末尾：
def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr 测试 arr = [64, 25, 12, 22, 11] print("排序前:", arr) print("排序后:", selection_sort(arr.copy()))时间复杂度：O(n²)
空间复杂度：O(1)
3.3 插入排序（Insertion Sort）
插入排序将每个元素插入到已排序部分的适当位置：
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr 测试 arr = [12, 11, 13, 5, 6] print("排序前:", arr) print("排序后:", insertion_sort(arr.copy()))时间复杂度：O(n²)
空间复杂度：O(1)
3.4 快速排序（Quick Sort）
快速排序使用分治策略，选择一个基准元素将数组分为两部分：
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) 测试 arr = [10, 7, 8, 9, 1, 5] print("排序前:", arr) print("排序后:", quick_sort(arr.copy()))时间复杂度：平均O(n log n)，最坏O(n²)
空间复杂度：O(log n)
3.5 归并排序（Merge Sort）
归并排序采用分治思想，将数组递归分成两半，然后合并排序：
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) 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 测试 arr = [38, 27, 43, 3, 9, 82, 10] print("排序前:", arr) print("排序后:", merge_sort(arr.copy()))时间复杂度：O(n log n)
空间复杂度：O(n)
4. 排序算法性能比较
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学示例，小规模数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据，交换次数少 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模或基本有序数据 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据，通用排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，需要稳定性 |
5. 实际应用建议
- 小规模数据（n < 100）：使用Python内置的
sort()或sorted()即可，底层采用TimSort算法，性能优秀 - 大规模数据：优先使用内置排序，Python的TimSort在大多数情况下表现优异
- 需要稳定性：选择归并排序或TimSort（Python内置排序是稳定的）
- 内存受限：考虑堆排序或原地快速排序
- 特殊数据结构：对于链表，插入排序和归并排序更合适
6. 总结
Python提供了强大且高效的排序功能，通过内置的sort()和sorted()函数可以满足大多数排序需求。理解经典排序算法的原理有助于在特殊场景下选择合适的排序策略。在实际开发中，建议优先使用Python内置排序方法，只有在特定需求（如教学、算法研究或特殊数据结构）时才考虑手动实现排序算法。
：Total War模组开发的终极解决方案深度解析)
