如何用Python实现常见的排序算法（快排、归并）？-Python教程-PHP中文网

如何用Python实现常见的排序算法（快排、归并）？

夢幻星辰

发布： 2025-09-04 19:54:01

原创

698人浏览过

快速排序的pivot选择策略包括随机选择和三数取中法，可提升算法效率；归并排序空间复杂度较高，可通过迭代实现或链表结构优化；算法选择需根据数据规模、特点、空间限制和稳定性要求综合考虑，实际中Python内置排序采用Timsort算法。

如何用python实现常见的排序算法（快排、归并）？

Python实现排序算法，核心在于理解算法逻辑并巧妙运用Python的特性。快速排序和归并排序是两种非常高效的排序算法，它们都基于分而治之的思想。

解决方案

直接上代码，然后我们再来聊聊细节：

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 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 += left[i:]
    result += right[j:]
    return result

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
print("快速排序:", quick_sort(arr.copy())) # 使用copy避免修改原数组
print("归并排序:", merge_sort(arr.copy()))

登录后复制

快速排序的pivot选择策略有哪些？

快速排序的关键在于

pivot

登录后复制

（枢轴）的选择。上面的代码中，我们简单地选择了中间元素。但实际上，

pivot

登录后复制

的选择会直接影响算法的效率。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

立即学习“Python免费学习笔记（深入）”；

随机选择： 随机选择
```
pivot
```
登录后复制
可以有效避免最坏情况的发生，使得算法在平均情况下表现良好。
三数取中： 选取数组的第一个、中间和最后一个元素，然后选择这三个数的中位数作为
```
pivot
```
登录后复制
。这种方法可以降低
```
pivot
```
登录后复制
选到极端值的概率。
优化思路： 在小规模数组中使用插入排序。当快速排序递归到小规模数组时，切换到插入排序往往更高效。

import random

def quick_sort_random_pivot(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[random.randint(0, len(arr) - 1)] # 随机选择pivot
    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_random_pivot(left) + middle + quick_sort_random_pivot(right)

arr = [3, 6, 8, 10, 1, 2, 1]
print("随机Pivot快速排序:", quick_sort_random_pivot(arr.copy()))

登录后复制

归并排序的空间复杂度如何优化？

归并排序的一个缺点是需要额外的空间来存储合并后的结果。虽然它保证了O(n log n)的时间复杂度，但在某些内存受限的场景下，空间复杂度会成为瓶颈。

原地归并（In-place Merge）： 理论上存在原地归并的实现，但实现起来非常复杂，且效率通常不如非原地归并。
链表结构： 如果数据存储在链表中，归并排序可以更容易地实现原地操作，因为链表的插入和删除操作不需要移动大量元素。
优化思路： 实际应用中，可以考虑使用迭代版本的归并排序，减少递归带来的额外空间开销。虽然无法完全消除额外空间，但可以降低其影响。

如何选择合适的排序算法？

没有绝对最好的排序算法，选择哪种算法取决于具体的应用场景和数据特点。

数据规模： 对于小规模数据，插入排序可能比快速排序和归并排序更快，因为它实现简单，且常数因子较小。
数据特点： 如果数据基本有序，插入排序或冒泡排序可能会有很好的性能。
空间限制： 如果对空间复杂度有严格要求，可以考虑堆排序，它是一种原地排序算法，空间复杂度为O(1)。
稳定性： 如果需要保持相等元素的相对顺序，可以选择归并排序或插入排序。快速排序是不稳定的。
实际应用： Python的
```
sorted()
```
登录后复制
函数和
```
list.sort()
```
登录后复制
方法通常使用Timsort算法，这是一种混合排序算法，它结合了归并排序和插入排序的优点，在实际应用中表现出色。