编程巅峰之路！Python算法揭秘：归并排序的魔力与实现技巧！

测试开发囤货

发布于 2023-08-08 09:29:44

1860

发布于 2023-08-08 09:29:44

文章被收录于专栏：测试开发囤货

编程巅峰之路！Python算法揭秘：归并排序的魔力与实现技巧！

归并排序

归并排序是一种基于分治思想的排序算法，它将待排序的列表分割成较小的子列表，然后递归地对子列表进行排序，最后将排好序的子列表合并以得到完整的有序列表。

算法步骤：

将待排序列表分割成长度相等（或相差最多1）的两个子列表。
递归地对两个子列表进行归并排序，直到子列表长度为1。
将排好序的子列表合并，得到一个新的有序列表。
重复步骤3，直到所有子列表都被合并成一个有序列表。

示例

下面是用Python编写的归并排序算法示例：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)


def merge(left, right):
    merged = []
    left_idx = 0
    right_idx = 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1

    while left_idx < len(left):
        merged.append(left[left_idx])
        left_idx += 1

    while right_idx < len(right):
        merged.append(right[right_idx])
        right_idx += 1

    return merged

# 测试示例
nums = [64, 25, 12, 22, 11]
sorted_nums = merge_sort(nums)
print("排序后的数组:", sorted_nums)

在这个示例中，我们定义了两个函数：merge_sort和merge。函数merge_sort接受一个列表arr作为输入，并通过递归地对子列表进行归并排序来对其进行排序。函数merge用于合并两个有序子列表。

可视化

现在让我们通过可视化展示归并排序算法的执行过程，以加深对算法的理解。

以下是归并排序的可视化示例：

原始数组: [64, 25, 12, 22, 11]

拆分过程:
[64, 25, 12, 22, 11] -> [64, 25] [12, 22, 11] -> [64] [25] [12] [22, 11] -> [64] [25] [12] [22] [11]

合并过程:
[64] [25] -> [25, 64]
[12] [22] [11] -> [11, 12, 22]
[25, 64] [11, 12, 22] -> [11, 12, 22, 25, 64]

排序后的数组: [11, 12, 22, 25, 64]

通过这个可视化示例，你可以看到归并排序算法是如何将列表分割成较小的子列表，并通过合并排好序的子列表来逐步构建有序列表的。