Python实现排序：从基础到高级的完整指南
在编程中，排序是一项非常重要的任务，几乎在所有应用程序中都会用到。排序算法用于将一个数据集按照某种顺序重新排列，比如升序、降序或自定义顺序。在Python中，排序有许多简单而强大的实现方法，从内置函数到自定义排序算法应有尽有。本文将带您全面了解如何在Python中实现排序，并深入探讨一些常见的排序算法。
1. 什么是排序？
排序是一种算法操作，其目的是将一组数据按照特定的顺序重新排列。排序算法的性能通常由时间复杂度和空间复杂度来衡量，常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。
2. Python内置的排序方法
Python提供了两种内置的排序方法：**sorted()函数和列表对象的sort()方法**。
2.1 使用 sorted() 函数
sorted() 是Python的一个内置函数，用于返回排序后的新列表。
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = sorted(numbers)
print(sorted_numbers) # 输出: [1, 2, 5, 5, 6, 9]
参数说明：
iterable：需要排序的可迭代对象。key：用于指定排序的规则，常用一个函数来定义。reverse：布尔值，默认为False，设置为True时结果为降序。
2.2 使用 sort() 方法
sort() 是列表对象的一个方法，直接对原列表进行排序，不返回新列表。
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort() # 原地排序
print(numbers) # 输出: [1, 2, 5, 5, 6, 9]
3. 自定义排序规则
通过key参数，可以定义排序的规则。key接收一个函数，该函数应用于每个元素来生成用于排序的值。
3.1 按字符串长度排序
words = ["banana", "apple", "cherry", "blueberry"]
sorted_words = sorted(words, key=len)
print(sorted_words) # 输出: ['apple', 'banana', 'cherry', 'blueberry']
3.2 按复杂规则排序
比如根据字母的倒序进行排序：
words = ["banana", "apple", "cherry", "blueberry"]
sorted_words = sorted(words, key=lambda x: x[::-1])
print(sorted_words) # 输出: ['banana', 'apple', 'blueberry', 'cherry']
4. 常见排序算法的Python实现
以下是一些常见的排序算法的Python实现，每种算法都有不同的优缺点。
4.1 冒泡排序
冒泡排序通过多次交换相邻元素，将最大的元素“冒泡”到末尾。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
numbers = [5, 2, 9, 1, 5, 6]
bubble_sort(numbers)
print(numbers) # 输出: [1, 2, 5, 5, 6, 9]
时间复杂度: O(n²)
适用场景: 小规模数据集。
4.2 选择排序
选择排序每次从未排序的部分找到最小值，然后将其放在已排序部分的末尾。
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]
numbers = [5, 2, 9, 1, 5, 6]
selection_sort(numbers)
print(numbers) # 输出: [1, 2, 5, 5, 6, 9]
时间复杂度: O(n²)
4.3 插入排序
插入排序通过构建一个有序的序列，将每个新元素插入到有序序列的正确位置。
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
numbers = [5, 2, 9, 1, 5, 6]
insertion_sort(numbers)
print(numbers) # 输出: [1, 2, 5, 5, 6, 9]
时间复杂度: O(n²)
适用场景: 数据接近有序时效率较高。
4.4 快速排序
快速排序是基于分治法的一种高效排序算法。
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)
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers) # 输出: [1, 2, 5, 5, 6, 9]
时间复杂度: 平均为 O(n log n)，最差为 O(n²)。
4.5 归并排序
归并排序是另一种分治算法，将数组分为两部分分别排序，然后合并。
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
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers) # 输出: [1, 2, 5, 5, 6, 9]
时间复杂度: O(n log n)。
5. 比较不同的排序算法
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | 稳定 | 小型数据集 |
| 选择排序 | O(n²) | O(n²) | 不稳定 | 简单实现 |
| 插入排序 | O(n²) | O(n²) | 稳定 | 数据接近有序时效率较高 |
| 快速排序 | O(n log n) | O(n²) | 不稳定 | 通用排序算法，高效 |
| 归并排序 | O(n log n) | O(n log n) | 稳定 | 大型数据集 |
