为什么我的合并排序程序不工作？

Question

为什么我的归并排序程序不工作？

def merge(a, p, q, r):
    n1 = (q - p) + 1
    n2 = r - q
    L = [0] * n1
    M = [0] * n2

    for i in range(n1):
        L[i] = a[i]

    for j in range(n2):
        M[j] = a[j]

    i = 0
    j = 0

    for k in range(p, r):
        if L[i] <= M[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = M[j]
            j += 1

def merge_sort(a, p, r):
    if len(a) <= 1:
        print('list has only one element')
    else:
        q = len(a) // 2
        merge_sort(a, p, q)
        merge_sort(a, q + 1, r)
        merge(a, p, q, r)

        
a = [3,41,52,26,38,57,9,49]
merge_sort(a, 0, len(a) - 1)
for _ in range(len(a)):
    print('%d', a[_])

Answer 1

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

切片的初始化循环不正确。 a 的索引应该分别从 p 和 q+1 开始。将它们更改为：
```
  for i in range(n1):
      L[i] = a[p+i]

  for j in range(n2):
      M[j] = a[q+1+j]
```
或者直接写：
```
  L = a[p..q+1]
  M = b[q+1..r+1]
```
这很明显 q 和 r 应该排除在外而不是包含在内。
合并循环不正确：范围应该是range(p, r+1)并且一旦其中一个临时数组耗尽，比较L[i] <= M[j]指的是超出其中一个边界的元素L 或 M.
q 在 merge_sort 中计算不正确：应该是 q = (p + r) // 2

测试 if len(a) <= 1: 不正确，您应该测试切片是否至少有 2 个元素，如果没有则什么也不做：

  if p < r:
      q = (p + r) // 2
      merge_sort(a, p, q)
      merge_sort(a, q + 1, r)
      merge(a, p, q, r)

这是一个排除了上限的修改版本：

def merge(a, p, q, r):
    L = a[p..q]
    M = a[q..r]

    i = 0
    j = 0

    for k in range(p, r):
        if j >= len(M) or (i < len(L) and L[i] <= M[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = M[j]
            j += 1

def merge_sort(a, p, r):
    if r - p > 1:
        q = p + (r - p) // 2
        merge_sort(a, p, q)
        merge_sort(a, q, r)
        merge(a, p, q, r)

        
a = [3,41,52,26,38,57,9,49]
merge_sort(a, 0, len(a))
for _ in range(len(a)):
    print('%d', a[_])

为什么我的合并排序程序不工作？

why my merge sort program is not working?

python

algorithm

mergesort