python 归并排序

假设有一个随机排序的list[]

事实上python的list.sort()可以直接排序，我们无视这个方法

递归程式  

# 归并排序法排序 列表实例
import random
 
def random_int_list(start, stop, length):
    start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
    length = int(abs(length)) if length else 0
    random_list = []
    for i in range(length):
        random_list.append(random.randint(start, stop))
    return random_list
 
#对2个有序数列进行排序的方法
def sort(list1,list2):
    new_list = []
    if len(list1) == 0:
        new_list = list2
    elif len(list2) == 0:
        new_list = list1
    else:
        while len(list1)>0 or len(list2)>0:
            if len(list1) == 0:
                new_list.extend(list2)
                list2.clear()
            elif len(list2) == 0:
                new_list.extend(list1)
                list1 .clear()
            elif list1[0] < list2[0]:
                new_list.append(list1[0])
                del list1[0]
            else:
                new_list.append(list2[0])
                del list2[0]
    #print (new_list)
    return new_list
 
def fun(list):
    if len(list)>=2:
        i = len(list)//2
        list1 = list[:i]
        list2 = list[i:]
        return sort(fun(list1),fun(list2))
    else:
        return list
 
 
list = random_int_list(0,1000,100)
 
print('old_list:%s'%list)
print('new_list:%s'%fun(list))

非递归排序，从底往上  

import random,math

def random_int_list(start, stop, length):
    start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
    length = int(abs(length)) if length else 0
    random_list = []
    for i in range(length):
        random_list.append(random.randint(start, stop))
    return random_list

def getlist(list,start,stop):
    if start>len(list):
        return []
    elif stop>len(list):
        return list[start:]
    else:
        return list[start:stop]

#对2个有序数列进行排序的方法
def sort(list1,list2):
    new_list = []
    if len(list1) == 0:
        new_list = list2
    elif len(list2) == 0:
        new_list = list1
    else:
        while len(list1)>0 or len(list2)>0:
            if len(list1) == 0:
                new_list.extend(list2)
                list2.clear()
            elif len(list2) == 0:
                new_list.extend(list1)
                list1 .clear()
            elif list1[0] <= list2[0]:
                new_list.append(list1[0])
                del list1[0]
            else:
                new_list.append(list2[0])
                del list2[0]
    return new_list

def fun(list):
    i = 1 #i为当前层级每个子列表的长度，即每次跨越长度

    while i < len(list):
        j = 0
        new_list = []
        while j <len(list):
            list1 = getlist( list, j ,j + i )
            list2 = getlist( list , j + i , j+ i*2 )
            new_list.extend(sort(list1,list2))
            j = j + i*2
        list = new_list
        i= 2*i
    return list

list = random_int_list(0,1000,25)

print('old_list:%s'%list)
print('new_list:%s'%fun(list))

归并排序