Python 合并排序算法的实现

Question

我遇到了 mergeSort 算法的以下实现：

def merge_sort(x):
    merge_sort2(x,0,len(x)-1)


def merge_sort2(x,first,last):
    if first < last:
        middle = (first + last) // 2
        merge_sort2(x,first,middle)
        merge_sort2(x,middle+1,last)
        merge(x,first,middle,last)


def merge(x,first,middle,last):
    L = x[first:middle+1]
    R = x[middle+1:last+1]
    L.append(999999999)
    R.append(999999999)
    i=j=0
    for k in range(first,last+1):
        if L[i] <= R[j]:
            x[k] = L[i]
            i += 1
        else:
            x[k] = R[j]
            j += 1


x = [17, 87, 6, 22, 41, 3, 13, 54]
x_sorted = merge_sort(x)
print(x)

我明白了大部分。但是，我不明白的是合并函数的以下四行：

 L = x[first:middle+1]
    R = x[middle+1:last+1]
    L.append(999999999)
    R.append(999999999)

首先：为什么切片以 middle+1 结束？在 Python 中切片数组包括最后一个元素，对吗？那么，从 first:middle 切片是否足够了？那么，+1 有什么用呢？其次：为什么我必须将巨大的数字附加到列表中？为什么没有它就不起作用？不会的，我查过了但我就是不知道为什么。

Answer 1

你真的不需要意大利面条式的嵌套函数，简单地 recur 就可以了，来自 https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python

from heapq import merge

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) // 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

索引不应该有 +1，因为 Python 如果索引相同，切片就不会重叠，即

>>> x = [1,2,3,4,5,6]
>>> middle = 4
>>> x[:middle]
[1, 2, 3, 4]
>>> x[middle:]
[5, 6]

此外，合并的 heapq 实现会比您编写的更优化 =)

Answer 2

问题 1：在 Python 中对数组进行切片包括最后一个元素，对吗？

不，像范围函数 Python 切片不包括最后一个元素。

> a=[1,2,3,4,5]
> a[1:4]
[2, 3, 4]

Q2：关于下面的片段。

 L = x[first:middle+1]
    R = x[middle+1:last+1]
    L.append(999999999)
    R.append(999999999)

如果不将这些大数字附加到列表中，您的合并代码可能会有所不同，如下所示。

   # Copy data to temp arrays L[] and R[] 
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            x[k] = L[i]
            i += 1
        else:
            x[k] = R[j]
            j += 1
    # Checking if any element was left 
    while i < len(L): 
        x[k] = L[i] 
        i+=1
        k+=1
    while j < len(R): 
        x[k] = R[j] 
        j+=1
        k+=1

正如@Cedced_Bro在评论区指出的那样，那些最大的数字是用来知道已经到达其中一侧的末端的。如果你观察上面的代码片段，如果我们运行超出了一个列表中的数字，我们理想地退出 for 循环并将其他列表的剩余元素插入到临时数组中（如果有的话）。

附加这些大数字是避免这两个 for 循环的明智方法。但是它有一些不必要的成本 999999999 与其他列表中的剩余元素进行比较。

Python 合并排序算法的实现

Python implementation of the mergeSort algorithm

python

mergesort