数据结构与算法之归并排序，以及它的代码实现与事例

目录

前言

定义

策略

代码

实现

结果

结束语

前言

今天是坚持写博客的第22天，我们来看看数据结构与算法当中的归并排序。

定义

首先我们来看看什么是归并排序？

归并排序（Merge Sort）是一种分治思想的排序算法。它将待排序的数组分成若干个子数组，每个子数组都是有序的，然后再将有序子数组合并成一个大的有序数组，直到合并为1个完整的数组。

策略

接下来是归并排序的策略实现。

合并是归并排序中的关键步骤。假设我们有两个已排序的子数组A和B，我们要将它们合并成一个大的有序数组C。合并的基本思想是，比较两个子数组的第一个元素，将较小的元素添加到C中，并移动相应子数组的指针到下一个位置。然后，重复这个过程，直到其中一个子数组的所有元素都被添加到C中，最后将另一个子数组的剩余元素添加到C的末尾。

具体方法：

1. 分解：将待排序的数组分解成两个较小的子数组，直到子数组的大小为1。子数组的大小为1时，我们认为它是已排序的（或称为“有序子数组”）。
2. 递归合并：递归地对子数组进行排序。将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。

假设我们有一个数组：[38，27， 43，3， 9， 82， 10]，我们现对他进行分解：将数组分解成单个元素的子数组。

然后对数组进行合并与排序，并在合并的过程中进行排序，例如38和27一组，在合并完成后就变成[27，38]。其他的也一样，同理。将两个两元素的数组排序时，也和单元素数组合并一样操作即可。

代码

接下来就是大家期待已久的代码实现，实现和运行结果如下： 

实现

def merge_sort(arr):  
    if len(arr) <= 1:  
        return arr  
  
    # 分解  
    mid = len(arr) // 2  
    left = arr[:mid]  
    right = arr[mid:]  
  
    # 递归进行排序  
    left = merge_sort(left)  
    right = merge_sort(right)  
  
    # 合并  
    return merge(left, right)  
  
  
def merge(left, right):  
    merged = []  
    left_index = 0  
    right_index = 0  
  
    # 比较两个数组的元素，并将较小的元素添加到merged数组中  
    while left_index < len(left) and right_index < len(right):  
        if left[left_index] <= right[right_index]:  
            merged.append(left[left_index])  
            left_index += 1  
        else:  
            merged.append(right[right_index])  
            right_index += 1  
  
    # 如果left数组还有剩余元素，将它们添加到merged数组中  
    while left_index < len(left):  
        merged.append(left[left_index])  
        left_index += 1  
  
    # 如果right数组还有剩余元素，将它们添加到merged数组中  
    while right_index < len(right):  
        merged.append(right[right_index])  
        right_index += 1  
  
    return merged  
  
  
# 示例  
arr = [38, 27, 43, 3, 9, 82, 10]  
sorted_arr = merge_sort(arr)  
print(sorted_arr)  # 输出: [3, 9, 10, 27, 38, 43, 82]

结果

结束语

今天对归并排序的解释就到这里，希望可以对大家有帮助。如果对您有帮助，希望您可以给我一个点赞、关注和收藏，这对我很重要，谢谢！