python排序算法之归并排序

让我来详细讲解一下“Python排序算法之归并排序”的完整攻略。

什么是归并排序？

归并排序是一种基于比较的排序算法，在最坏情况下时间复杂度也为 $O(n\log_2n)$。它采用分而治之的思想，将待排序数组分成若干个子数组，逐层合并，最终得到有序的结果。归并排序的核心思想是把一个大问题分解成若干个小的问题解决，直到小问题不可分解，再把所有小问题的结果合并成一个大问题的结果。

实现步骤

1. 判断序列 halflen = len(arr) // 2 是否达到最小粒度，如果达到则无需再排序，返回原序列。
2. 对序列进行二分拆分： arr_left, arr_right = arr[:halflen], arr[halflen:]
3. 对 arr_left, arr_right 重复 1-2 操作，直到样本粒度为1。
4. 合并 arr_left, arr_right: 新建一个 list，同时对两个序列进行依序比较，小数先入新 list，直到其中一个序列为空。在将另一个序列中的剩余元素全部入新序列，最后返回新序列。

代码示例

下面是一个 Python 实现归并排序的示例代码：

def merge(arr_left, arr_right):
    i, j = 0, 0
    result = []
    while i < len(arr_left) and j < len(arr_right):
        if arr_left[i] < arr_right[j]:
            result.append(arr_left[i])
            i += 1
        else:
            result.append(arr_right[j])
            j += 1
    result += arr_left[i:]
    result += arr_right[j:]
    return result

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)

示例说明

下面是两个示例，分别介绍了归并排序的具体实现以及如何使用归并排序。

示例1 - 定义归并排序函数

在这个示例中，我们定义了一个名为 merge_sort 的归并排序函数，该函数接收一个待排序的数组，返回一个排好序的数组。该函数采用分治策略，先将原始数组递归分为左右两个数组，再将左右两个数组合并为一个有序数组，最后返回合并后的数组。

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)

示例2 - 使用归并排序排序数组

在这个示例中，我们使用 merge_sort 函数来对一个数组进行排序。数组 [3, 5, 1, 4, 2] 将被传给 merge_sort 函数，最终会返回排好序的数组 [1, 2, 3, 4, 5]。

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

输出结果： [1, 2, 3, 4, 5]。

至此，我们已经完成了“Python排序算法之归并排序”的完整攻略，希望能对你有所帮助。