#Python数据结构与算法——归并排序

概述归并排序概念与原理归并排序的思想是先拆分，再组合，组合的同时进行排序，最后组合成一个新的有序序列拆分，将序列拆到每一份只有一个元素合并，合并的顺序是怎么拆的怎么合，比如由[54,26]拆成了[54]，[26]，合并的时候就是他们两个合，54对应一个left_pointer游标，26对应right_pointer游 归并排序概念与原理

归并排序的思想是先拆分，再组合，组合的同时进行排序，最后组合成一个新的有序序列

拆分，将序列拆到每一份只有一个元素

合并，合并的顺序是怎么拆的怎么合，比如由[54, 26]拆成了[54]，[26]，合并的时候就是他们两个合，54对应一个left_pointer游标，26对应right_pointer游标，比较两个游标对应元素的大小，若左边比右边大，则left_pointer与right_pointer对应的元素互换

游标进行互换 *** 作之后均需要往后移一位，直到移到最后，将未移完的一侧的所有元素放到新序列的后面

重复这样的融合过程，直到融合为一个序列，此时序列为有序序列

实现

def merge_sort(aList):    """归并排序"""    n = len(aList)    if n <= 1:  # 当拆分拆分拆到序列中只有一个元素时，返回这个序列        return aList    mID = n // 2    # left 采用归并排序后形成的新的有序列表    left_li = merge_sort(aList[:mID])    # right 采用归并排序后形成的新的有序列表    right_li = merge_sort(aList[mID:])    # 将两个有序子序列合并成一个新的整体    # merge(left, right)    left_pointer, right_pointer = 0, 0    result = []    while left_pointer < len(left_li) and right_pointer < len(right_li):        if left_li[left_pointer] >= right_li[right_pointer]:            result.append(right_li[right_pointer])            right_pointer += 1        else:            result.append(left_li[left_pointer])            left_pointer += 1    # 跳出循环时，有一个游标指向了拆分列表的最后一位的下一位（这一位不存在，但是循环时加到了下一位），需要将另一个序列剩余的所有元素加到result中    result += left_li[left_pointer:]    result += right_li[right_pointer:]    return resultif __name__ == "__main__":    li = [66, 22, 55, 44, 11, 99, 77, 33, 88]    print(li)    merge = merge_sort(li)    print(li)    print(merge)    # 运行结果：# [66, 22, 55, 44, 11, 99, 77, 33, 88]# [66, 22, 55, 44, 11, 99, 77, 33, 88]# [11, 22, 33, 44, 55, 66, 77, 88, 99]

归并排序的时间复杂度最优时间复杂度：O(nlogn)最坏时间复杂度：O(nlogn)稳定性：稳定

在进行归并排序的时候，无所谓最坏还是最优情况，一视同仁，所有情况都需要走一遍，因此时间复杂度都是nlogn，以2为底

常见排序算法效率比较

一定需要掌握的是快速排序，它的时间复杂度更趋近于nlogn，且不需要像归并排序一样拿出一块内存单独的地方来进行存储

剩下的任意掌握一两种即可（要会原理，要会把算法写出来）

 

 

 

 

 

 

 

总结

以上是内存溢出为你收集整理的#Python数据结构与算法——归并排序全部内容，希望文章能够帮你解决#Python数据结构与算法——归并排序所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。