Python 数据排序：详解各种排序算法及应用200

Python 提供了多种方法对数据进行排序，从内置函数到自定义算法，选择合适的排序方法取决于数据的特性、规模以及性能要求。本文将深入探讨 Python 中的各种排序方法，包括其原理、适用场景以及代码示例，帮助读者掌握 Python 数据排序的技巧。

一、内置排序函数 `sorted()` 和 `()`

Python 提供了两个内置函数用于排序：`sorted()` 和 `()`。两者功能相似，但关键区别在于 `sorted()` 返回一个新的已排序列表，而 `()` 直接修改原列表，并返回 `None`。这在内存管理和代码风格上有所不同。

sorted() 函数：接受一个可迭代对象作为参数，返回一个新的已排序列表。例如：```python
my_list = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_list = sorted(my_list)
print(f"Original list: {my_list}")
print(f"Sorted list: {sorted_list}")
```

() 方法：直接修改原列表，没有返回值。例如：```python
my_list = [3, 1, 4, 1, 5, 9, 2, 6]
()
print(f"Sorted list: {my_list}")
```

这两个函数都支持 `key` 和 `reverse` 参数。`key` 参数指定一个函数，用于从每个元素中提取用于比较的值；`reverse` 参数指定是否反向排序。```python
data = [('apple', 2), ('banana', 1), ('cherry', 3)]
sorted_data = sorted(data, key=lambda x: x[1]) # 排序依据第二个元素
print(sorted_data) # Output: [('banana', 1), ('apple', 2), ('cherry', 3)]
sorted_data_reverse = sorted(data, key=lambda x: x[0], reverse=True) # 按第一个元素逆序排序
print(sorted_data_reverse) # Output: [('cherry', 3), ('banana', 1), ('apple', 2)]
```

二、常用的排序算法

除了内置函数，Python 也能实现各种排序算法，理解这些算法有助于选择最优方案。

1. 冒泡排序 (Bubble Sort)：是一种简单的排序算法，重复地走访待排序的列表，比较相邻的元素，并交换它们如果它们是错误的顺序。重复直到列表已排序。```python
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]
return arr
my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print("Sorted array:", sorted_list)
```

2. 插入排序 (Insertion Sort)：构建最终排序数组的一个有序子序列。每次迭代通过从输入数据中移除一个元素，并将其插入到已排序子序列中的适当位置。重复直到所有的输入数据元素已插入已排序子序列。```python
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
my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = insertion_sort(my_list)
print("Sorted array:", sorted_list)
```

3. 选择排序 (Selection Sort)：重复找到最小元素，并将其放置到数组的开头。该算法不稳定。```python
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
my_list = [64, 25, 12, 22, 11, 90]
sorted_list = selection_sort(my_list)
print ("Sorted array is:", sorted_list)
```

4. 快速排序 (Quick Sort)：是一种高效的排序算法，选择一个基准值，并将数组分成两部分：小于基准值和大于基准值。递归地排序这两部分。平均时间复杂度为 O(n log n)，最坏情况下为 O(n^2)。```python
def quick_sort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
my_list = [10, 7, 8, 9, 1, 5]
sorted_list = quick_sort(my_list)
print("Sorted array is:", sorted_list)
```

5. 合并排序 (Merge Sort)：一种稳定的排序算法，将数组递归地分成两半，直到每个子数组只有一个元素。然后，将这些子数组合并成已排序的数组。时间复杂度为 O(n log n)。```python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
my_list = [12, 11, 13, 5, 6, 7]
sorted_list = merge_sort(my_list)
print("Sorted array is:", sorted_list)
```