Python 合并排序

Question

我正在尝试实现 Python 合并排序，但我在某些方面失败了。我拥有的伪代码是准确的，但看起来它是为另一种语言构建的。

伪需要以下内容
/声明输入数组 a

大小的数组临时值

我不确定在 Python 中这怎么可能。无论如何，代码如下。整个想法是我需要对 array/list 和 return 排序。

截至目前，它失败并显示以下消息。我会说这是因为新的温度array/list，但我不确定

Traceback (most recent call last):  
  File "./mergesort", line 56, in <module>  
    main()  
  File "./mergesort", line 52, in main  
    mergesortbase(array)  
  File "./mergesort", line 4, in mergesortbase  
    mergesort(num, 0, len(num)-1)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 12, in mergesort  
    merge(num, low, mid, mid+1, high)  
  File "./mergesort", line 27, in merge  
    temp[k] = a[j]  
IndexError: list assignment index out of range

注意：完全修改代码没有帮助，因为我需要使用完全相同的伪代码。

#!/usr/bin/python3.6

def mergesortbase(num):
    mergesort(num, 0, len(num)-1)


def mergesort(num, low, high):
    if low < high:
      mid = (low + high) // 2
      mergesort(num, low, mid)
      mergesort(num, mid+1, high)
      merge(num, low, mid, mid+1, high)

def merge(a, l1, u1, l2, u2):
# declare array temp of size of input array a
# Comment -- Not doable in Python to create array/list with specific size
    temp = []
    i = l1
    j = l2
    k = l1

    while (i <= u1 and j <= u2):
      if (a[i] <= a[j]):
         temp[k] = a[i]
         i = i + 1
      else:
         temp[k] = a[j]
         j = j + 1

      k = k + 1

    while ( i <= u2 ):
       temp[k] = a[i]
       k = k + 1
       i = i + 1

    while ( j <= u2 ):
       temp[k] = a[j]
       k = k + 1
       i = i + 1

    h = l1

    while ( h <= u2 ):
       a[h] = temp[h]
       h = h + 1


def main():
   array = [8, 5, 7, 1, 9, 3]
   mergesortbase(array)


if __name__ == "__main__":
  main()

Answer 1

你能复制输入数组吗？

温度=a.copy()

大小相同。

如果你想将 temp 中的所有元素初始化为某个值，请使用类似的东西：

temp = [0] * len(a)

Answer 2

我很好奇您为什么不直接使用 Python 的内置排序功能，可以根据需要使用 sort 或 sorted。它可能比您自己滚动的东西更有效（除非您在数据集上使用特定的额外信息，这里似乎不是这种情况）。可能您这样做是出于教育目的，在这种情况下，请随意忽略此段落，但如果您的意图是不提及内置内容，我会失职只是对一些数据进行排序。

无论如何，您的具体问题似乎是如何 "declare array temp of size of input array a"。

这很容易用语句完成：

temp = [0] * len(a)

以下记录显示了这一点：

>>> a = [1,2,3]
>>> temp = [0] * len(a)
>>> temp
[0, 0, 0]

你现在拥有的是：

temp = []

创建一个大小为零的列表，后跟：

temp[k] = a[i]

这总是会导致问题，因为没有 k 的值可以工作。

最重要的是，您的实际合并存在缺陷，因为您使用了不正确的变量来处理数组。您已经非常合乎逻辑地将某些项目联系在一起，例如 i 与第一个数组部分，以及 j 与第二个部分，但是稍后您违反了：

while ( i <= u2 ):  # i and u1 should be associated: while i <= u1:
   temp[k] = a[i]   # (no need for '()' in Python conditions by the way).
   k = k + 1
   i = i + 1

while ( j <= u2 ):
   temp[k] = a[j]
   k = k + 1
   i = i + 1        # j and u2 should be associated: j = j + 1

即使您修复了数组创建，上面的第二个循环也可能会导致问题。它将永远运行（或直到异常，以先到者为准），因为您正在检查 j 但永远不会更改它。但是，以上项都不正确，因此应予以修正。

一旦我将数组设置为正确的大小，进行这两个更改，并打印出排序前后的数组，它似乎好一点：

[8, 5, 7, 1, 9, 3]
[1, 3, 5, 7, 8, 9]

Answer 3

您的代码中存在三个错误

temp 未初始化为任何大小，因此 k 始终给出 list assignment index out of range
用于将剩余元素 l1 添加到 u1 的第二个 while 循环需要运行直到 u1 而不是 u2:

用于将剩余元素从 l2 添加到 u2 的第三个 while 循环需要递增 j 而不是 i。

def merge(a, l1, u1, l2, u2):
    temp = [0]*len(a)
    i = l1
    j = l2
    k = l1
    while (i <= u1 and j <= u2):
        if (a[i] <= a[j]):
            temp[k] = a[i]
            i = i + 1
        else:
            temp[k] = a[j]
            j = j + 1

        k = k + 1
    while ( i <= u1 ):
        temp[k] = a[i]
        k = k + 1
        i = i + 1
    while ( j <= u2 ):
        temp[k] = a[j]
        k = k + 1
        j = j + 1

    h = l1

    while ( h <= u2 ):  
        a[h] = temp[h]
        h = h + 1

Answer 4

看看这个，应该能得到理解合并排序所需的答案

MergeSort

Python 合并排序

Python MergeSort

python

mergesort

list

pseudocode