基于Python的归并排序（分治算法）实现二维数组排序

需求说明 #

输入二维数组，需对每个子数组分别使用归并排序完成升序排列，示例如下：

输入：array = [['b', 'a', 'c'], [2, 1, 3]]
输出：array = [['a', 'b', 'c'], [1, 2, 3]]

实现代码 #

def merge(left, right):
    merged = []
    i = j = 0
    # 比较左右两个有序数组的元素，依次加入结果
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # 处理剩余未加入的元素
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def merge_sort(arr):
    # 递归终止条件：数组长度小于等于1时已有序
    if len(arr) <= 1:
        return arr
    # 分治：将数组拆分为左右两半
    mid = len(arr) // 2
    left_sorted = merge_sort(arr[:mid])
    right_sorted = merge_sort(arr[mid:])
    # 合并两个有序子数组
    return merge(left_sorted, right_sorted)

def sort_2d_array(arr):
    # 遍历二维数组的每个子数组，分别应用归并排序
    return [merge_sort(sub_arr) for sub_arr in arr]

# 测试示例
if __name__ == "__main__":
    input_array = [['b', 'a', 'c'], [2, 1, 3]]
    sorted_array = sort_2d_array(input_array)
    print(sorted_array)  # 输出：[['a', 'b', 'c'], [1, 2, 3]]

代码说明 #

• merge函数：核心是合并两个已排序的子数组，通过双指针遍历比较元素大小，保证合并后的数组仍然有序，最后处理剩余未遍历完的元素。
• merge_sort函数：实现分治逻辑，递归将数组拆分为左右两部分，直到子数组长度为1（天然有序），再逐层调用merge合并有序子数组。
• sort_2d_array函数：遍历输入的二维数组，对每个子数组单独执行归并排序，最终返回处理后的二维数组。

内容的提问来源于stack exchange，提问作者Mok