Python实现Merge Sort无输出疑似陷入无限循环问题排查

核心问题 #

你的代码陷入无限循环的根源是：第一个while循环中遇到左右元素均为奇数时，i和j指针都不递增，循环条件永远成立。此外，归并逻辑仅处理了部分偶数场景，未覆盖所有情况，也未明确奇数的处理规则，导致逻辑混乱。

解决方案 #

根据你“合并后列表中的偶数按降序排列返回”的需求，提供两种修复方案：

方案1：仅保留偶数并降序排序（推荐） #

先从合并数组中过滤出所有偶数，再对偶数执行标准归并降序排序，彻底规避奇数带来的循环问题：

def leer_vector(lis, n):
    for x in range(n):
        lis.append(int(input("Ingrese el dato: ")))
    return lis

cd = int(input("Ingrese la cantidad de datos: "))
v1 = []
v2 = []
leer_vector(v1, cd)
leer_vector(v2, cd)

v3 = v1 + v2

def merge_sort_even_desc(arr):
    # 过滤出所有偶数
    even_arr = [num for num in arr if num % 2 == 0]
    
    def merge_sort(arr):
        if len(arr) > 1:
            mid = len(arr) // 2
            left = arr[:mid]
            right = arr[mid:]
            
            merge_sort(left)
            merge_sort(right)
            
            i = j = k = 0
            # 归并降序：取较大的偶数放入当前位置
            while i < len(left) and j < len(right):
                if left[i] > right[j]:
                    arr[k] = left[i]
                    i += 1
                else:
                    arr[k] = right[j]
                    j += 1
                k += 1
            
            # 处理剩余未合并的偶数
            while i < len(left):
                arr[k] = left[i]
                i += 1
                k += 1
            while j < len(right):
                arr[k] = right[j]
                j += 1
                k += 1
        return arr
    
    return merge_sort(even_arr)

# 调用并打印结果
sorted_evens = merge_sort_even_desc(v3)
print("偶数降序排列结果:", sorted_evens)

方案2：保留原数组所有元素，仅偶数降序 #

如果需要保留原数组中的奇数，仅将偶数部分按降序排列，可使用以下逻辑：

def leer_vector(lis, n):
    for x in range(n):
        lis.append(int(input("Ingrese el dato: ")))
    return lis

cd = int(input("Ingrese la cantidad de datos: "))
v1 = []
v2 = []
leer_vector(v1, cd)
leer_vector(v2, cd)

v3 = v1 + v2

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        merge_sort(left)
        merge_sort(right)
        
        # 收集左右子数组中的偶数并降序排序
        left_evens = [num for num in left if num % 2 == 0]
        right_evens = [num for num in right if num % 2 == 0]
        sorted_evens = sorted(left_evens + right_evens, reverse=True)
        even_ptr = 0
        
        i = j = k = 0
        # 重构数组：奇数保留原位置，偶数替换为排序后的值
        while i < len(left) and j < len(right):
            if left[i] % 2 != 0:
                arr[k] = left[i]
                i += 1
            elif right[j] % 2 != 0:
                arr[k] = right[j]
                j += 1
            else:
                arr[k] = sorted_evens[even_ptr]
                even_ptr += 1
                i += 1
                j += 1
            k += 1
        
        # 处理左子数组剩余元素
        while i < len(left):
            if left[i] % 2 != 0:
                arr[k] = left[i]
            else:
                arr[k] = sorted_evens[even_ptr]
                even_ptr += 1
            i += 1
            k += 1
        
        # 处理右子数组剩余元素
        while j < len(right):
            if right[j] % 2 != 0:
                arr[k] = right[j]
            else:
                arr[k] = sorted_evens[even_ptr]
                even_ptr += 1
            j += 1
            k += 1

merge_sort(v3)
print("保留奇数、偶数降序结果:", v3)

方案3：最小改动修复原代码无限循环 #

如果不想大幅修改原代码，仅修复无限循环问题，可在第一个while循环中添加奇数处理分支：

# 仅修改merge_sort函数中的第一个while循环
while i < len(leftarr) and j < len(rightarr):
    left_is_even = leftarr[i] % 2 == 0
    right_is_even = rightarr[j] % 2 == 0
    
    if left_is_even and right_is_even:
        # 两个都是偶数，取较大的
        if leftarr[i] > rightarr[j]:
            arr[k] = leftarr[i]
            i += 1
        else:
            arr[k] = rightarr[j]
            j += 1
        k += 1
    elif left_is_even:
        # 左偶右奇，取左偶数
        arr[k] = leftarr[i]
        i += 1
        k += 1
    elif right_is_even:
        # 右偶左奇，取右偶数
        arr[k] = rightarr[j]
        j += 1
        k += 1
    else:
        # 两个都是奇数，跳过并移动指针
        i += 1
        j += 1

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