3回答

liuyubobobo

2016-12-04

已采纳

太棒了！这么做是可以的，很好的优化！虽然仍然需要开辟临时空间，但是减少了一半的数组复制时间，而且写起来也并不复杂，可以自己实现看一看比较一下。优化的时间不会特别明显，但一定是有效的！：）

这样做和递归退出条件无关啊。_merge函数本身本身不是一个递归函数。他要做的事情就是将数组的两个有序部分归并成为一个有序的部分。_mergeSort才是递归函数。而你的方法优化了_merge的过程，并不需要修改_mergeSort的递归退出条件。事实上，整个_mergeSort的逻辑都不需要改变：）

5

0

ywang04

2017-02-21

楼上同学用的Python实现的 我这边也用Python实现了一版 供参考

import SortTestHelper

def merge(left, right, A):
    i = 0
    j = 0
    k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1
        k += 1
    while i < len(left):
        A[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        A[k] = right[j]
        j += 1
        k += 1

def mergeSort(A,n):
    if n < 2:
        return
    else:
        mid = n / 2
        left = A[:mid]
        right = A[mid:]
        mergeSort(left,len(left))
        mergeSort(right,len(right))
        merge(left, right, A)
        
if __name__=='__main__':
    n = 50000
    arr = SortTestHelper.generateRandomList(0,n,n)
    SortTestHelper.testSort("Merge Sort",mergeSort,arr,n)

2

2

ywang04

回复

liuyubobobo

谢谢老师鼓励 大家继续加油~

2017-02-22

共2条回复

8280

提问者

2016-12-05

附上原函数和改进后的函数：

def _merge(arr,l,mid,r):

    temp=[]

    for i in range(l,r+1):

        temp.append(arr[i])

    a=l 

    b=mid+1

    for i in range(l,r+1):

        if(a>mid):

            arr[i]=temp[b-l]

            b+=1

        elif(b>r):

            arr[i]=temp[a-l]

            a+=1

        elif(temp[a-l]>temp[b-l]):

            arr[i]=temp[b-l]

            b+=1

        else:

            arr[i]=temp[a-l]

            a+=1

def _merge2(arr,l,mid,r):

    temp=[]

    for i in range(l,mid+2):

        temp.append(arr[i])

    a=l 

    b=mid+1

    for i in range(l,r+1):

        if(a>mid):

            arr[i]=arr[b]

            b+=1

        elif(b>r):

            arr[i]=temp[a-l]

            a+=1

        elif(temp[a-l]>arr[b]):

            arr[i]=arr[b]

            b+=1

        else:

            arr[i]=temp[a-l]  

            a+=1

0

0