mergeSort算法的Python实现

2024-03-28 14:52:18 发布

您现在位置:Python中文网/ 问答频道 /正文

我遇到了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中切片数组包括最后一个元素,对吗?那么,难道不应该从第一:中间?那么,+1有什么用呢? 第二:为什么我要把这个巨大的数字附加到清单上?为什么没有它就不能工作?没有,我查过了。但我不知道为什么。你知道吗


Tags: in算法middleforlenifdef切片
2条回答

实际上,您并不需要意大利面条式的嵌套函数,只要从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]

此外,merge的heapq实现比您可以编写的更为优化(=)

问题1:在Python中对数组进行切片包括最后一个元素,对吗?

不,像范围函数Python切片不包括最后一个元素。你知道吗

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

问题2:关于下面的片段。你知道吗

 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\u Bro在评论部分指出的那样,那些最大的数字被用来知道一方的终点已经到达。 如果您观察上面的代码片段,如果一个列表中的数字用完了,那么理想情况下,我们会退出for循环,并在temp数组中插入其他列表的剩余元素(如果有的话)。你知道吗

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

相关问题 更多 >