Python 归并排序算法教程

了解如何在 Python 中实现归并排序。分而治之排序策略的交互式分步示例。

在编辑器中尝试

概述

归并排序是一种高效的排序算法，采用分而治之的策略。它将未排序的列表分解为更小的子列表，对这些子列表进行排序，然后将它们合并在一起。

该算法递归地将数组分成两半，直到达到单元素子数组。然后，它通过比较每一侧的元素并将它们按排序顺序放置，来合并排序的子数组。这确保了最佳的时间复杂度。

无论初始数组是排序的、反转的还是完全随机的，归并排序都会在 O(n log n) 时间内执行。然而，在合并阶段需要 O(n) 额外空间来保存子列表。

代码和执行输出

Python 中合并排序算法的标准递归实现。

merge_sort.py

在编辑器中尝试

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 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

# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List:  ", sorted_data)

端子输出

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

逐步实施

对链表进行排序，其中节点结构便于轻松合并，无需复制
针对不完全适合系统 RAM 的文件的外部排序例程
稳定的排序应用程序，其中匹配键必须保留其原始顺序

常见问题解答

归并排序是一种稳定的排序算法吗？

是的，归并排序是稳定的。当比较相同的元素时，左侧（原始第一个）子数组中的元素被放置在前面，保留它们原始的相对位置。

为什么Python使用Timsort而不是纯粹的归并排序？

Python 内置的“sorted()”使用 Timsort，这是一种结合了归并排序和插入排序的混合算法。它通过识别已经排序的子段来优化现实世界的数据模式，比纯粹的合并排序更快地呈现它。