python 问题中的合并排序

Question

def mergeSort(A, l, r):
    if l < r:
        mid = (l + r) // 2
        mergeSort(A, l, mid)
        mergeSort(A, mid + 1, r)
        merge(A, l, mid, r)

def merge(arr, l, mid, r):
    arr1 = []
    arr2 = []

    for i in range(mid):
        arr1.append(arr[i])

    for j in range(mid, r):
        arr2.append(arr[j])

    i = 0
    j = 0
    k = 0

    while (i < len(arr1) and j < len(arr2)):
        if arr1[i] < arr2[j]:
            arr[k] = arr1[i]
            i += 1
        else:   
            arr[k] = arr2[j]
            j += 1
        k += 1

    while i < len(arr1):
        arr[k] = arr1[i]
        i += 1
        k += 1

    while j < len(arr2):
        arr[k] = arr2[j]
        j += 1
        k += 1


arr = [2, 9, 7, 6, 1, 8, 4, 3]
mergeSort(arr, 0, 8)

print(arr)

代码中某处有一个我找不到的小错误请尝试运行在您的机器上使用不同的测试用例来执行此代码。让我知道我在这里做错了什么。我不知道为什么我得到的答案不正确：[1, 2, 3, 4, 6, 8, 9, 7]

Answer 1

    else:   
        arr[k] = arr2[j]
        j += 1
    k += 1

更改位置 k += 1 对此：

    else:   
        arr[k] = arr2[j]
        j += 1
        k += 1

或者这样：

    else:   
        arr[k] = arr2[j]
        j += 1
k += 1

Answer 2

您的索引有问题。你用 C 风格写了代码。只需使用切片即可解决您的问题

将 arr1 和 arr2 的定义（删除 arr1 和 arr2 的 for 循环）更改为：

arr1 = arr[:mid]
arr2 = arr[mid:]

Answer 3

您的代码中存在多个问题：

您将要排序的第一个元素的索引传递给切片的最后一个元素后的索引，但是您编写的函数 mergeSort 具有不同的语义，因为您假设 r 是切片最后一个元素的索引。
类似地，merge 期望 mid 参数是右半部分的开始，而您传递 mid，这将是上半部分最后一个元素的索引在你的方法中。
在merge函数中，arr1应该初始化为i，从l到mid，for i in range(l:mid):
此外，k必须初始化为l，而不是0。
请注意 arr1 和 arr2 可以从 arr 的简单切片初始化。

这是修改后的版本：

def mergeSort(A, l, r):
    if r - l > 1:
        mid = (l + r) // 2
        mergeSort(A, l, mid)
        mergeSort(A, mid, r)
        merge(A, l, mid, r)

def merge(arr, l, mid, r):
    arr1 = arr[l : mid]
    arr2 = arr[mid : r]

    i = 0
    j = 0
    k = l

    while (i < len(arr1) and j < len(arr2)):
        if arr1[i] <= arr2[j]:
            arr[k] = arr1[i]
            i += 1
        else:
            arr[k] = arr2[j]
            j += 1
        k += 1

    while i < len(arr1):
        arr[k] = arr1[i]
        i += 1
        k += 1

    while j < len(arr2):
        arr[k] = arr2[j]
        j += 1
        k += 1

arr = [2, 9, 7, 6, 1, 8, 4, 3]
mergeSort(arr, 0, 8)

print(arr)

输出：

[1, 2, 3, 4, 6, 7, 8, 9]

python 问题中的合并排序

Merge sort in python issue

python

sorting

mergesort