python基本算法之实现归并排序(Merge sort)

1. 什么是归并排序

归并排序（Merge sort）是一种常见的排序算法，基于分治法的思想。它将一个待排序的列表递归地拆分成较小的子列表，直到每个子列表只含有一个元素，然后将这些子列表逐个合并起来，直到最后只有一个有序的列表。

2. 归并排序的算法步骤

归并排序的算法步骤如下：

2.1 拆分

将待排序的列表不断地二分拆分，直到每个子列表只含有一个元素。

2.2 合并

将相邻的两个子列表进行合并，同时保持合并后的列表有序。

2.3 递归

重复执行步骤2.1和2.2，直到合并到只剩下一个有序的列表。

3. 归并排序的实现

下面是使用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.extend(left[i:])
    result.extend(right[j:])
    
    return result

4. 示例

下面是使用归并排序算法对一个列表进行排序的示例：

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

运行上述代码，输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

5. 分析

归并排序的平均时间复杂度为O(nlogn)，其中n是待排序列表的长度。虽然归并排序的时间复杂度较高，但它具有稳定性和可靠性。同时，归并排序是一种稳定排序算法，适用于各种类型的数据。

6. 总结

归并排序是一种常见的排序算法，通过分治法的思想将一个待排序的列表递归地拆分成较小的子列表，然后将这些子列表逐个合并起来，最终得到一个有序的列表。归并排序的时间复杂度为O(nlogn)，适用于各种类型的数据。