Python实现归并排序(Merge Sort)运行返回空列表问题求助
归并排序手写实现返回空列表的调试说明
核心错误定位
- 缩进语法错误,直接阻断运行流程
merge函数末尾的return (resultList)未缩进到函数代码块层级,属于全局作用域下的顶层代码。Python不允许在函数外执行return,会直接触发语法报错;即便手动修正缩进把return移入函数块,当前合并逻辑也无法产出有效结果。 - 递归终止条件逻辑偏差
mergeSort中的递归终止判断设置为if len(alist) > 2,意味着列表长度≤2时会直接返回原列表,不做任何排序处理。长度为0、1的列表虽天然有序,但长度为2的列表未经过比较交换的排序步骤,后续合并流程的基础数据本身就是无序的。 - 合并模块完全偏离归并排序核心逻辑
归并排序的合并操作核心是:对两个已经完成升序排序的子列表,通过双指针从左到右依次对比指针位置的元素,将更小的元素追加到结果列表,直到某一个子列表遍历完成,再将另一个子列表的剩余元素直接拼接在结果末尾。当前合并实现存在多处错位:- 循环边界使用
range(len(子列表)-1),直接遗漏每个子列表最后一个元素的遍历 - 循环内反复对传入的
left、right原列表执行remove操作,会直接修改递归链上已经排好序的子列表对象,破坏数据一致性 - 最小值对比逻辑错位:当前代码是在单个子列表内部循环找最小值,完全没有跨两个子列表做双指针对比,反复删除子列表元素的操作最终会把传入的子列表清空,直接导致返回结果列表为空。
- 循环边界使用
- 边界场景逻辑缺失
当传入的子列表长度为1时,代码中计算的len(right)-1、len(left)-1结果为0,生成的循环范围为空集,无法进入内层找最小值的分支,leastLeft、leastRight会一直保留初始值0,只要子列表存在比0小的元素,对比逻辑就会完全失效。
可正常运行的参考实现
def merge(left, right): resultList = [] left_idx = 0 right_idx = 0 # 双指针对比两个有序子列表 while left_idx < len(left) and right_idx < len(right): if left[left_idx] <= right[right_idx]: resultList.append(left[left_idx]) left_idx += 1 else: resultList.append(right[right_idx]) right_idx += 1 # 拼接剩余未遍历的元素 resultList.extend(left[left_idx:]) resultList.extend(right[right_idx:]) return resultList def mergeSort(alist): # 递归终止:列表长度≤1时天然有序 if len(alist) <= 1: return alist middleIndex = len(alist) // 2 sortedLeft = mergeSort(alist[:middleIndex]) sortedRight = mergeSort(alist[middleIndex:]) return merge(sortedLeft, sortedRight) # 测试用例 print("mergesort", mergeSort([6, 0, 2, 8, 9, 1]))
内容的提问来源于stack exchange,提问作者Daniel Todd
相关产品推荐
相关产品推荐

