Python实现快速排序与插入排序详解及自定义排序技巧

快速排序原理与实现

快速排序（Quicksort）采用分治思想，由C. A. R. Hoare于1962年提出。其核心流程为：选取基准元素将数据划分为小于等于和大于两部分，分别对子序列递归排序，最终拼接成有序序列。该方法在实际工程中通常具有较优的平均性能。

def quick_sort(arr):
    """快速排序（递归实现）"""
    if not arr:
        return []
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 测试用例
data = [3, 1, 4, 1, 5, 9, 2, 6]
print(quick_sort(data))
# 输出: [1, 1, 2, 3, 4, 5, 6, 9]

代码通过列表推导式简化了划分逻辑，基础条件判断确保空输入安全返回。递归终止依赖于子序列规模不断缩小至零。

插入排序原理与实现

插入排序（Insertion Sort）是一种稳定且直观的原地排序算法。它将数组视为已排序与未排序两部分，每次取出未排序首元素，在已排序区域从后向前扫描，找到合适位置并插入。该算法额外空间复杂度为O(1)，适合小规模或基本有序的数据集。

def insert_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 = [12, 11, 13, 5, 6]
print(insert_sort(data))
# 输出: [5, 6, 11, 12, 13]

循环从第二个元素开始遍历，内层while负责将比当前值大的已排序元素逐一右移，腾出空间后填入目标值。此实现严格遵循标准插入排序逻辑，避免盲目交换带来的性能损耗。

使用Key参数实现自定义排序

Python内置的list.sort()方法与全局函数sorted()均支持通过key参数接收可调用对象，以决定比较依据。借助该特性，可实现按特定权重、外部映射表或非默认规则排序。

# 基于预设目标顺序进行自定义排序
def custom_sort_by_index():
    raw_data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
    target_order = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
    
    # 使用lambda绑定索引作为排序键
    result = sorted(raw_data, key=lambda x: target_order.index(x))
    print(result)
    
if __name__ == '__main__':
    custom_sort_by_index()
    # 输出: [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]

示例中，lambda表达式将每个元素映射至目标列表中的索引位置，sorted()据此生成新序列。若需频繁排序同类数据，建议预先构建字典映射以提升检索效率，避免在key函数中重复调用线性查找。

总结

快速排序依托分治策略提供高效的平均时间复杂度，插入排序凭借稳定的原地操作适用于局部有序场景，而Python的key参数则为业务定制化排序提供了极简入口。掌握这三类基础实现，可覆盖多数常规数据结构整理需求。以上就是Python实现快速排序与自定义排序详解的详细内容，更多关于Python排序算法实战的资料请关注本站其它相关文章！