Python排序算法详解及代码实现325

Python作为一门功能强大的编程语言，在数据处理方面拥有丰富的库和工具。排序是数据处理中最常见且基础的操作之一，本文将深入探讨Python中常用的排序算法，并提供详细的代码实现及性能分析，帮助读者更好地理解和应用这些算法。

排序算法大致可以分为两类：内部排序和外部排序。内部排序指的是数据全部存储在内存中进行排序，而外部排序则需要将数据存储在外部存储器（如硬盘）中进行排序。本文主要关注内部排序算法，因为它们在大多数Python应用场景中更为常见。

1. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并交换它们以使较大的元素“浮动”到列表的末尾。虽然简单易懂，但冒泡排序的效率很低，时间复杂度为O(n^2)，不适合处理大量数据。```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
arr = [64, 34, 25, 12, 22, 11, 90]
print("Sorted array:", bubble_sort(arr))
```

2. 选择排序 (Selection Sort)

选择排序也是一种简单的排序算法，它重复地找到未排序部分中的最小元素，并将其与未排序部分的第一个元素交换。它的时间复杂度同样为O(n^2)，效率也不高，但它在空间复杂度方面表现出色，为O(1)。```python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr = [64, 25, 12, 22, 11, 90]
print("Sorted array:", selection_sort(arr))
```

3. 插入排序 (Insertion Sort)

插入排序的工作原理类似于我们整理扑克牌的方式。它从第二个元素开始，将每个元素插入到前面已排序的子序列中的正确位置。插入排序的时间复杂度在最坏情况下为O(n^2)，但在近乎有序的数据中表现良好，时间复杂度接近O(n)。```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
arr = [12, 11, 13, 5, 6]
print("Sorted array:", insertion_sort(arr))
```

4. 归并排序 (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
arr = [12, 11, 13, 5, 6, 7]
print("Sorted array:", merge_sort(arr))
```

5. 快速排序 (Quick Sort)

快速排序也是一种基于分治思想的排序算法，它选择一个元素作为“枢轴”，将列表分成两部分：小于枢轴的元素和大于枢轴的元素。然后递归地对这两部分进行排序。快速排序的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。```python
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j]

2025-04-20

上一篇：Python文件操作：从创建到高级技巧

下一篇：Python高效读写与修改文件：详解常用方法及最佳实践