2022-09-19

python 代码写归并排序，是面试中常考的

有两种方式，一种是递归的，一种是迭代的

递归的，利用了切片，代码行数很少

def gui(la,a,e):
    if a<e:
        m=a+e>>1
        gui(la,a,m)
        gui(la,m+1,e)
        he(a,m,e)

def he(a,m,e):
    i,j,t=a,m+1,[]
    while i<=m and j<=e:
        if la[i]<=la[j]:
            t.append(la[i])
            i+=1
        else:
            t.append(la[j])
            j+=1
    la[a:e+1]=t+la[i:m+1]+la[j:e+1]

la =[11, 3, 44, 6, 45, 5, 68, 7, 9] 
gui(la,0,len(la)-1)
print(la)

下面的是迭代的，，step 倍增的

def guibing(la):
    def he(a,b,c,d):
        m,t=a,[]
        while a<b and c<d:
            if la[a]<=la[c]:
                t.append(la[a])
                a+=1 
            else:
                t.append(la[c])
                c+=1
        la[m:d] = t + la[a:b] + la[c:d]    

    n=len(la)
    step =1 
    while step < n:
        i=f=0 
        while i < n:
            start,stop  = i,i+step  
            if stop>n:
                stop =n 
            if f:
                f=0
                he(a,b,start,stop)
            else: 
                f=1 
                a=start
                b=stop
            i+=step

        step+=step


x = [11, 3, 44, 6, 45, 5, 68, 7, 9]
guibing(x)
print(x)