【算法图解】学习笔记5——归并排序

简介：

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为n*log n。

1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

采用分治法:

• 分割：递归地把当前序列平均分割成两半。

• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

代码实现

def merge(left,right):#合并两个列表

    merge_arr=[]

    i=0

    j=0

    l=len(left)

    r=len(right)

#i分别作为left和right的下标,分别获取左右子列表的长度

    while i<l and j<r:#循环归并左右子列表元素

        if left[i]<right[j]:

            merge_arr.append(left[i])

            i+=1

        else:

            merge_arr.append(right[j])

            j+=1

    merge_arr.extend(left[i:])

    merge_arr.extend(right[j:])

    #归并左子列表剩余元素

    #归并右子列表剩余元素

    #返回归并好的列表

    # print('左数组为：{}'.format(left),'右数组为{}'.format(right),'合并数组为{}'.format(merge_arr))

    return merge_arr

def RealSortQuick(input_arr):#拆分+合并

    if len(input_arr)<=1:

        return input_arr

    else:

        mid=int(len(input_arr)/2)

        left=RealSortQuick(input_arr[0:mid])

        right=RealSortQuick(input_arr[mid:])

        #合并排好序的左右两个子列表

        return merge(left,right)

myarr=[24,34,2,3,567,34,65,78,863,421,23]

RealSortQuick(myarr)