Python 插入排序教程
最后修改于 2025年3月8日
在本文中，我们将解释插入排序算法，并演示其在 Python 中的实现。我们还将它与快速排序算法进行比较。
算法是解决问题或执行计算的逐步过程。算法是计算机科学的基础，用于处理数据、执行计算和自动化任务。
排序 是以特定顺序（例如升序或降序）排列数据的过程。排序对于高效的数据检索和分析至关重要。
常用排序算法
一些常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
插入排序
插入排序是一种简单的排序算法，它一次构建一个项目的最终排序数组。 它对于小型数据集是有效的，但对于大型数据集是低效的。
插入排序示例
以下 Python 代码演示了插入排序算法。
insertion_sort.py
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
# Sorting numeric data in ascending order
numbers = [12, 11, 13, 5, 6]
insertion_sort(numbers)
print("Sorted numbers (ascending):", numbers)
# Sorting textual data in ascending order
words = ["apple", "banana", "cherry", "date"]
insertion_sort(words)
print("Sorted words (ascending):", words)
# Sorting numeric data in descending order
def insertion_sort_desc(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
insertion_sort_desc(numbers)
print("Sorted numbers (descending):", numbers)
# Sorting textual data in descending order
insertion_sort_desc(words)
print("Sorted words (descending):", words)
该代码对数字和文本数据进行升序和降序排序。
说明
插入排序算法的工作原理是迭代列表，并将每个元素插入到列表中已排序部分的正确位置。
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
insertion_sort 函数按升序对数组进行排序。
def insertion_sort_desc(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
insertion_sort_desc 函数按降序对数组进行排序。
插入排序与快速排序的比较
对于小型数据集，插入排序是有效的，但对于较大的数据集，其时间复杂度为 O(n²)。 另一方面，快速排序的平均时间复杂度为 O(n log n)，对于较大的数据集效率更高。
benchmark.py
import time
import random
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
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)
# Generate a large dataset
data = [random.randint(1, 1000) for _ in range(1000)]
# Benchmark insertion sort
start_time = time.time()
insertion_sort(data.copy())
insertion_time = time.time() - start_time
# Benchmark quick sort
start_time = time.time()
quick_sort(data.copy())
quick_time = time.time() - start_time
print(f"Insertion Sort Time: {insertion_time:.6f} seconds")
print(f"Quick Sort Time: {quick_time:.6f} seconds")
该基准测试比较了插入排序和快速排序在大型数据集上的性能。
来源
在本文中，我们解释了插入排序算法，并演示了其在 Python 中的实现。
作者
列出所有 Python 教程。