时间戳

首页 > 解决方案 > 实现归并排序算法以升序对数字列表进行排序

python - 实现归并排序算法以升序对数字列表进行排序

问题描述

我试图在python中实现合并排序，这就是我得到的：

def merge_sort(num_list):
    if len(num_list) < 2:
        return num_list
    else:
        mid = len(num_list) // 2
        left_list = merge_sort(num_list[: mid])
        right_list = merge_sort(num_list[mid: ])
        merge(left_list,right_list)

def merge(left_list,right_list):
    sorted_list = []
    i = j = 0
    while (i < len(left_list) and j < len(right_list)):
        if left_list[i] <= right_list[j]:
            sorted_list.append(left_list[i])
            i += 1
        else:
            sorted_list.append(right_list[j])
            j += 1
    while(i < len(left_list)):
        sorted_list.append(left_list[i])
        i += 1
    while j < len(right_list):
        sorted_list.append(right_list[j])
        j += 1
    return sorted_list

我收到了这个错误信息：

Traceback (most recent call last):
line 34, in <module>
sorted_list = merge_sort(num_list)
line 9, in merge_sort
left_list=merge_sort(num_list[:mid])
line 12, in merge_sort
merge(left_list,right_list)
line 18, in merge
while i<len(left_list) and j<len(right_list):
TypeError: object of type 'NoneType' has no len()

有人可以帮我理解代码中出了什么问题，我该如何解决？

标签： pythondata-structuresmergesort

解决方案

You're not returning the merged list in your merge_sort method in your else condition. The following change will make your function work correctly (note the return at the end):

def merge_sort(num_list):
    if len(num_list) < 2:
        return num_list
    mid = len(num_list) // 2
    left_list = merge_sort(num_list[: mid])
    right_list = merge_sort(num_list[mid: ])
    return merge(left_list,right_list)

推荐阅读