合并排序算法的困难

Question

我正在努力理解和实现合并排序。我运行在这方面陷入困境，似乎无法获得有效的实施。我当前的实施遇到 "list index out of range" 错误。这是我的代码：

def merge_sort(list_a):
    mid = len(list_a) // 2
    print('Mid is ', mid)
    while len(list_a) > 1:
        left = list_a[:mid]
        print('Left is now ', left)
        right = list_a[mid:]
        print('Right is now ', right)
        merge_sort(left)
        merge_sort(right)
        merge(list_a, left, right)


def merge(comb_list, list_a, list_b):
    print('Starting the merge.')
    a1, b1, c1 = 0, 0, 0
    na, nb, nc = len(list_a), len(list_b), len(comb_list)
    while a1 < na and b1 < nb:
        if list_a[a1] < list_b[b1]:
            print('Adding from A')
            comb_list[c1] = list_a[a1]
            a1 += 1
        else:
            print('Adding from B')
            comb_list[c1] = list_b[b1] 
            b1 += 1

        c1 += 1

    while list_a:
        comb_list[c1] = list_a[a1]
        c1 += 1
        a1 += 1

    while list_b:
        comb_list[c1] = list_b[b1]
        c1 += 1
        b1 += 1

if __name__ == '__main__':
    list_a = [54,26,93,17,77,31,44,55,20]
    merge_sort(list_a)

Answer 1

我已对您的脚本进行了三处更改以使其正常运行。正如 sshdup while list_a 所指出的那样，由于您没有删除循环内的任何元素，因此将始终评估为 true 。因此我将while list_a:改为len(list_a)>a1，while list_b:改为len(list_b)>b1。我还根据 pseudo code 将 return merge(list_a, left, right) 添加到您的 merge_sort 方法中。添加 return 语句后， merge_sort 中的 while 也可以替换为 if 语句。我已经在随机整数数组上对此进行了测试，它似乎可以工作，但是，像往常一样，您应该测试边缘情况以确保它按预期工作。

def merge_sort(list_a):
    mid = len(list_a) // 2
    print('Mid is ', mid)
    if len(list_a) > 1:
        left = list_a[:mid]
        print('Left is now ', left)
        right = list_a[mid:]
        print('Right is now ', right)
        merge_sort(left)
        merge_sort(right)
        return merge(list_a, left, right)


def merge(comb_list, list_a, list_b):
    print('Starting the merge.')
    a1, b1, c1 = 0, 0, 0
    na, nb, nc = len(list_a), len(list_b), len(comb_list)
    while a1 < na and b1 < nb:
        if list_a[a1] < list_b[b1]:
            print('Adding from A')
            comb_list[c1] = list_a[a1]
            a1 += 1
        else:
            print('Adding from B')
            comb_list[c1] = list_b[b1] 
            b1 += 1

        c1 += 1

    while len(list_a)>a1:
        comb_list[c1] = list_a[a1]
        del list_a[a1]
        c1 += 1
        a1 += 1

    while len(list_b)>b1:
        comb_list[c1] = list_b[b1]        
        c1 += 1
        b1 += 1

if __name__ == '__main__':
    list_a = [54,26,93,17,77,31,44,55,20]
    merge_sort(list_a)
    print list_a

Answer 2

要使代码正常工作，您必须进行 2 处调整：

将第 4 行的 while 循环替换为 if 语句
稍微更改 merge() 函数中 while 循环的代码

工作代码：

def merge_sort(list_a):
    mid = len(list_a) // 2
    print('Mid is ', mid)
    #Use if statement instead
    if len(list_a) > 1:
        left = list_a[:mid]
        print('Left is now ', left)
        right = list_a[mid:]
        print('Right is now ', right)
        merge_sort(left)
        merge_sort(right)
        merge(list_a, left, right)
        #Print the result
        print(list_a)
        #Or return it directly:
        #return list_a


def merge(comb_list, list_a, list_b):
    print('Starting the merge.')
    a1, b1, c1 = 0, 0, 0
    na, nb, nc = len(list_a), len(list_b), len(comb_list)
    while a1 < na and b1 < nb:
        if list_a[a1] < list_b[b1]:
            print('Adding from A')
            comb_list[c1] = list_a[a1]
            a1 += 1
        else:
            print('Adding from B')
            comb_list[c1] = list_b[b1] 
            b1 += 1

        c1 += 1
    #Change while loop:
    while a1 < na:
        comb_list[c1] = list_a[a1]
        c1 += 1
        a1 += 1
    #Change while loop:
    while b1 < nb:
        comb_list[c1] = list_b[b1]
        c1 += 1
        b1 += 1

if __name__ == '__main__':
    list_a = [54,26,93,17,77,31,44,55,20]
    merge_sort(list_a)

您可能想直接 return 结果，只需添加

return list_a

在 merge_sort() 函数的末尾。使用这种方法，您可以在 main 方法中使用 print(merge_sort(list_a)) 直接打印结果。

合并排序算法的困难

Difficulty with merge sort algorithm

python

mergesort