归并排序实现

思路

将原始数组（相当于列表）切分为较小的数组单元，将小数组进行排序，再合并小数组，最终得到一个排序好的大数组。

实现

    def merge(left,right):#左右列表合并函数  
        li=0  
        ri=0  
        result=[]  
        # 定义左、右列表循环变量，以及一个空列表  
        while(li<len(left) and ri<len(right)):#循环左右列表，如果其中两列表中一个完成循环则跳出循环  
            if left[li]>right[ri]:#按下标依此比较，将比较后小的值加入到列表result中  
                result.append(right[ri])  
                ri+=1  
            else:  
                result.append(left[li])  
                li += 1  
        while li<len(left):#循环结束后，如果左列表未循环完，将其剩余的元素依次加入列表result中  
            result.append(left[li])  
            li+=1  
        while ri<len(right):#循环结束后，如果右列表未循环完，将其剩余的元素依次加入列表result中  
            result.append(right[ri])  
            ri+=1  
        return result  


    def merge_sort(ar):  
        if(len(ar)==1):  
            return ar#递归结束条件，即当前列表不可再切分  
        lenth = len(ar)  
        mid = int(lenth / 2)  
        left = ar[0: mid]  
        right = ar[mid:lenth]  
        return merge(merge_sort(left), merge_sort(right))  

    lt=[1,5,6,4,7,8]#定义一个要排序的列表  
    print(merge_sort(lt))#打印排序结果

结果：

    [1, 4, 5, 6, 7, 8]  

    Process finished with exit code 0