Python插入排序案例如何代码实现

wen python案例 2026-06-30 212

本文目录导读：

Python插入排序案例如何代码实现

基础插入排序实现
带详细注释的版本
优化版本（二分查找插入）
综合示例：不同数据类型的排序
性能测试
使用示例
算法特点

我来给你介绍插入排序的Python实现,包括基础版本和优化版本。

基础插入排序实现

def insertion_sort(arr):
    """
    插入排序基础实现
    时间复杂度: O(n²)
    空间复杂度: O(1)
    """
    # 遍历数组，从第二个元素开始
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i - 1     # 已排序部分的最后一个索引
        # 将key与已排序部分从后往前比较
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 元素后移
            j -= 1
        arr[j + 1] = key  # 插入key到正确位置
    return arr
# 测试
if __name__ == "__main__":
    numbers = [64, 34, 25, 12, 22, 11, 90]
    print("原始数组:", numbers)
    sorted_numbers = insertion_sort(numbers.copy())
    print("排序后数组:", sorted_numbers)

带详细注释的版本

def insertion_sort_detailed(arr):
    """
    插入排序（带详细注释）
    就像整理扑克牌一样，每次将一张牌插入到已排序的手牌中
    """
    # 从第2个元素开始（索引1），因为第1个元素（索引0）默认已排序
    for i in range(1, len(arr)):
        current = arr[i]  # 当前要插入的元素
        position = i      # 记录插入位置
        print(f"第{i}轮: 要插入的元素 = {current}")
        print(f"已排序部分: {arr[:i]}")
        # 在已排序部分从右向左查找插入位置
        while position > 0 and arr[position - 1] > current:
            arr[position] = arr[position - 1]  # 较大元素后移
            position -= 1
        # 插入当前元素到正确位置
        arr[position] = current
        print(f"插入后: {arr}\n")
    return arr
# 测试带详细注释的版本
numbers = [5, 2, 4, 6, 1, 3]
print("排序过程演示:")
print(f"初始数组: {numbers}\n")
result = insertion_sort_detailed(numbers.copy())
print(f"最终结果: {result}")

优化版本（二分查找插入）

import bisect
def insertion_sort_optimized(arr):
    """
    优化版本：使用二分查找快速定位插入位置
    但元素移动的时间复杂度仍然是O(n)
    """
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        # 在已排序部分[0:i]中查找key应该插入的位置
        left, right = 0, i
        while left < right:
            mid = (left + right) // 2
            if arr[mid] <= key:
                left = mid + 1
            else:
                right = mid
        # 将元素右移，为新元素腾出位置
        for j in range(i, left, -1):
            arr[j] = arr[j - 1]
        arr[left] = key
    return arr
# 测试
test_arr = [3, 8, 2, 5, 1, 4, 7, 6]
print(f"原始数组: {test_arr}")
result = insertion_sort_optimized(test_arr.copy())
print(f"排序后数组: {result}")

综合示例：不同数据类型的排序

def generic_insertion_sort(arr, key=lambda x: x, reverse=False):
    """
    通用插入排序：支持自定义排序规则
    """
    arr = arr.copy()  # 避免修改原数组
    for i in range(1, len(arr)):
        current = arr[i]
        j = i - 1
        # 根据reverse参数决定比较方式
        while j >= 0:
            if reverse:
                if key(arr[j]) < key(current):
                    arr[j + 1] = arr[j]
                    j -= 1
                else:
                    break
            else:
                if key(arr[j]) > key(current):
                    arr[j + 1] = arr[j]
                    j -= 1
                else:
                    break
        arr[j + 1] = current
    return arr
# 测试不同类型的排序
if __name__ == "__main__":
    # 1. 整数排序
    numbers = [64, 34, 25, 12, 22, 11, 90]
    print("整数排序:")
    print(f"升序: {generic_insertion_sort(numbers)}")
    print(f"降序: {generic_insertion_sort(numbers, reverse=True)}")
    # 2. 字符串排序
    words = ["banana", "apple", "cherry", "date"]
    print(f"\n字符串排序:")
    print(f"升序: {generic_insertion_sort(words)}")
    print(f"按长度排序: {generic_insertion_sort(words, key=len)}")
    # 3. 字典排序
    students = [
        {"name": "Alice", "score": 85},
        {"name": "Bob", "score": 92},
        {"name": "Charlie", "score": 78}
    ]
    sorted_by_score = generic_insertion_sort(
        students, 
        key=lambda s: s["score"]
    )
    print(f"\n按成绩排序:")
    for student in sorted_by_score:
        print(f"  {student['name']}: {student['score']}")

性能测试

import time
import random
def performance_test():
    """比较不同排序算法的性能"""
    # 生成测试数据
    sizes = [100, 500, 1000, 2000, 5000]
    for size in sizes:
        # 生成随机数组
        arr = [random.randint(1, 10000) for _ in range(size)]
        # 测试插入排序
        arr_copy = arr.copy()
        start = time.time()
        insertion_sort(arr_copy)
        time_insertion = time.time() - start
        # 测试Python内置排序
        arr_copy2 = arr.copy()
        start = time.time()
        arr_copy2.sort()
        time_builtin = time.time() - start
        print(f"n={size:5}: 插入排序={time_insertion:.6f}s, "
              f"内置排序={time_builtin:.6f}s, "
              f"比例={time_insertion/time_builtin:.2f}")
# 运行性能测试（注意：当数据量较大时可能会比较慢）
# performance_test()

使用示例

# 简单使用示例
arr = [12, 11, 13, 5, 6, 7]
print(f"排序前: {arr}")
insertion_sort(arr)
print(f"排序后: {arr}")
# 结果:
# 排序前: [12, 11, 13, 5, 6, 7]
# 排序后: [5, 6, 7, 11, 12, 13]