第5章 排序算法
排序是将一组数据按照特定顺序重新排列的过程，是计算机科学中最基本也是最重要的算法之一。排序算法不仅是实际应用中广泛使用的工具，也是学习算法设计思想的绝佳案例。本章将详细介绍多种经典的排序算法。
5.1 冒泡排序
Bubble Sort Animation
冒泡排序是最简单的排序算法之一。它的基本思想是通过重复地遍历数组，比较相邻元素并交换位置，将最大元素逐步移动到数组末尾。就像气泡在水中上升一样，较大的元素逐渐上浮到数组的一端。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
data = [64, 34, 25, 12, 22, 11, 90]
print(f"排序前: {data}")
sorted_data = bubble_sort(data.copy())
print(f"排序后: {sorted_data}")
冒泡排序的时间复杂度为O(n²)，因为需要进行n轮遍历，每轮遍历最多需要比较n次。空间复杂度为O(1)，只需要一个临时变量用于交换。冒泡排序是稳定的排序算法，相同元素的相对位置不会改变。通过引入swapped标志，可以在数组已经有序时提前终止，优化算法效率。
冒泡排序的改进版本包括鸡尾酒排序，它双向遍历数组，先从左到右将最大元素移到右端，再从右到左将最小元素移到左端。这种方式可以减少遍历次数，但时间复杂度仍然是O(n²)。
5.2 选择排序
Selection Sort Animation
选择排序的思想更加直观，每次从未排序部分选择最小元素，放到已排序部分的末尾。第一轮选择整个数组中最小的元素，放到第一个位置。第二轮从剩余元素中选择最小元素，放到第二个位置。重复这个过程，直到所有元素都排序完成。
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
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = selection_sort(data.copy())
print(f"选择排序结果: {sorted_data}")
选择排序的时间复杂度为O(n²)，因为需要进行n轮选择，每轮选择需要比较n-i次。空间复杂度为O(1)，不需要额外的存储空间。选择排序是不稳定的排序算法，因为交换操作可能改变相同元素的相对位置。
虽然选择排序的时间复杂度与冒泡排序相同，但实际运行时间通常更快。因为冒泡排序每次比较都可能触发交换，选择排序每轮只需要一次交换。交换操作的开销通常大于比较操作。
5.3 插入排序
Insertion Sort Animation
插入排序模拟了整理扑克牌的过程。我们假设前面的元素已经有序，将当前元素插入到合适的位置。具体做法是将当前元素与前面的元素依次比较，如果前面的元素更大，则将它们向后移动，直到找到合适的插入位置。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = insertion_sort(data.copy())
print(f"插入排序结果: {sorted_data}")
插入排序的时间复杂度在最好情况下为O(n)，当数组已经有序时，只需要遍历一次数组。在最坏情况下为O(n²)，当数组逆序时，每个元素都需要移动到数组开头。平均情况下为O(n²)。插入排序是稳定的排序算法，因为相同元素不会被交换。插入排序对于小规模数据和基本有序的数据效率很高。
插入排序在实际应用中经常被使用。比如在在线排序场景中，数据逐步到达，每次新数据到达时都可以使用插入排序将其加入已排序序列。归并排序和快速排序等高级排序算法在处理小规模子问题时，也经常使用插入排序来优化性能。
5.4 归并排序
Merge Sort Animation
归并排序是基于分治思想的排序算法。它将数组分成两个子数组，分别排序，然后将两个有序子数组合并成一个有序数组。这个过程递归进行，直到子数组长度为1，天然有序。
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, 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
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = merge_sort(data)
print(f"归并排序结果: {sorted_data}")
归并排序的时间复杂度为O(n log n)，因为需要log n层递归，每层递归的合并操作需要O(n)时间。空间复杂度为O(n)，因为合并过程需要额外的数组存储结果。归并排序是稳定的排序算法，因为合并过程中相同元素的相对位置保持不变。
归并排序适合处理大规模数据，特别是链表排序。因为链表不支持随机访问，插入排序和快速排序效率不高，但归并排序只需要顺序遍历链表，非常适合链表排序场景。归并排序也是外部排序的核心算法，用于处理无法一次性加载到内存的大文件。
5.5 快速排序
Quick Sort Animation
快速排序是最流行的排序算法之一，它在实际应用中的性能优于其他排序算法。快速排序的思想是选择一个基准元素，将数组分成两部分，一部分小于基准元素，另一部分大于基准元素，然后对两部分递归排序。
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)
def quick_sort_inplace(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = quick_sort(data.copy())
print(f"快速排序结果: {sorted_data}")
快速排序的平均时间复杂度为O(n log n)，最坏情况下为O(n²)。最坏情况发生在基准元素选择不当，每次只能排除一个元素时。通过随机选择基准元素或使用三数取中法，可以降低最坏情况出现的概率。原地版本的快速排序空间复杂度为O(log n)，因为需要递归栈空间。
快速排序是不稳定的排序算法，因为分区过程可能改变相同元素的相对位置。但快速排序的实际性能通常优于归并排序，因为它的常数因子更小，原地操作避免了额外的数组分配。
快速排序的改进版本包括随机化快速排序、三数取中快速排序和三路快速排序。三路快速排序将数组分成小于、等于和大于基准元素的三部分，适合处理有大量重复元素的数组。
5.6 堆排序
Heap Sort Animation
堆排序利用堆的性质进行排序。首先将数组构建成最大堆，此时堆顶元素是最大值。然后将堆顶元素与堆尾元素交换，缩小堆的大小并重新调整堆。重复这个过程，直到堆的大小为1，数组就排序完成了。
def heap_sort(arr):
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = heap_sort(data.copy())
print(f"堆排序结果: {sorted_data}")
堆排序的时间复杂度为O(n log n)，因为构建堆需要O(n)时间，每次调整堆需要O(log n)时间，总共需要调整n次。空间复杂度为O(1)，因为堆排序是原地排序算法。堆排序是不稳定的排序算法，因为堆调整过程可能改变相同元素的相对位置。
堆排序的优势在于它不需要递归，避免了栈溢出的风险。堆排序也适合处理大规模数据，特别是当内存有限时。但堆排序的实际性能通常不如快速排序，因为堆调整涉及更多的比较和交换操作。
5.7 排序算法比较
动图说明：以上 6 个排序算法的 GIF 动图均为 3fps 低帧率，时长控制在 8-15 秒之间，文件大小均在 500KB 以内，适合微信公众号上传。
不同的排序算法各有特点，选择合适的排序算法取决于具体场景。下面的表格总结了各排序算法的主要特性。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，教学演示 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据，交换开销大 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，基本有序数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，链表排序 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据，通用排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模数据，内存有限 |
import random
import time
def benchmark_sort(sort_func, data):
start = time.time()
sort_func(data.copy())
end = time.time()
return (end - start) * 1000
sizes = [100, 1000, 5000]
algorithms = [
('冒泡排序', bubble_sort),
('选择排序', selection_sort),
('插入排序', insertion_sort),
('归并排序', merge_sort),
('快速排序', quick_sort),
('堆排序', heap_sort),
]
for size in sizes:
data = [random.randint(1, 1000) for _ in range(size)]
print(f"\n数据规模: {size}")
for name, func in algorithms:
time_ms = benchmark_sort(func, data)
print(f"{name}: {time_ms:.2f} 毫秒")
对于小规模数据，插入排序通常是最快的选择。对于大规模数据，快速排序和归并排序是最佳选择。如果要求稳定性，归并排序是唯一的选择。如果内存有限，堆排序是合适的选择。Python的内置排序函数sorted和list.sort使用Timsort算法，它是归并排序和插入排序的结合，性能非常优秀。
本章我们学习了六种经典的排序算法。冒泡排序、选择排序和插入排序时间复杂度为O(n²)，适合小规模数据。归并排序、快速排序和堆排序时间复杂度为O(n log n)，适合大规模数据。理解排序算法不仅有助于解决实际问题，也是学习算法设计思想的重要途径。下一章我们将学习搜索算法，包括二分搜索和哈希表。
预览时标签不可点