mergeSort算法的Python实现 [英] Python implementation of the mergeSort algorithm

问题描述

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

I came across the following implementation of the mergeSort algorithm:

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)

我大部分都得到了.但是，我不理解的是合并功能的以下四行:

I get most of it. However, what I don't understand are the following four lines of the merge function:

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

首先:为什么切片以 middle + 1 结尾?在Python中切片数组包括最后一个元素，对吗?因此，从first:middle切片是否足够?那么， +1 有什么用呢? 其次:为什么我必须将大量数字附加到列表中?为什么没有它就不起作用?没有，我检查了一下.但是我只是不知道为什么.

First of all: why does the slicing end with middle+1 ? Slicing an array in Python includes the last element, right? So, shouldn't it be sufficient to slice from first:middle ? So, what is the +1 there for? Secondly: Why do I have to append the huge number to the lists? Why doesn't it work without? It doesn't, I checked that. But I just don't know why.

推荐答案

Q1:在Python中切片数组包括最后一个元素，对吧?

否，类似范围函数Python切片不包含最后一个元素.

No, Like range function Python slicing doesn't include the last element.

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

第二季度:关于以下代码段.

Q2: Regarding the below snippet.

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

如果不将这些大数字附加到列表中，则您的合并代码可能与下面的内容有所不同.

Without appending those large numbers to the lists, your merge code could have been different something like below.

   # 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循环，并将其他列表的其余元素插入到temp数组(如果有)中.

As @Cedced_Bro pointed out in the comment section, those largest numbers are used to know that the end of one of the sides has been reached. If you observe the above code snippet, if we run out of numbers in one list we ideally get out of the for loop and inserts the remaining elements of other lists in the temp array if any.

附加这些大数字是避免这两个for循环的明智方法.但这会造成不必要的比较，即999999999与其他列表中的其余元素的比较.

Appending those large numbers is an intelligent way to avoid those two for loops. But it has some cost of unnecessary comparison of 999999999 with remaining elements in the other list.

这篇关于mergeSort算法的Python实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！