python 实现归并排序算法

下面是关于“Python实现归并排序算法”的完整攻略。

1. 归并排序算法简介

归并排序是一种基于分治思想的排序算法，它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。

2. 归并排序算法实现

下面是Python实现归并排序算法的代码：

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

在这个代码中，我们定义了两个函数：merge_sort()和merge()。merge_sort()函数用于将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。merge()函数用于将两个有序的子序列合并成一个有序的序列。

3. 归并排序算法示例

下面是两个示例，演示了如何使用Python实现归并排序算法。

3.1 示例一

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)

在这个示例中，我们定义了一个待排序的序列arr，然后使用merge_sort()函数对其进行排序。最后，我们使用print()函数输出排序后的序列。

3.2 示例二

arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
sorted_arr = merge_sort(arr)
print(sorted_arr)

在这个示例中，我们定义了一个待排序的序列arr，然后使用merge_sort()函数对其进行排序。最后，我们使用print()函数输出排序后的序列。

4. 总结

归并排序是一种基于分治思想的排序算法，它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。Python实现归并排序算法的代码非常简单，只需要定义两个函数：merge_sort()和merge()。归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。