归并排序（Merge Sort）-- 高级排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了归并排序（Merge Sort）-- 高级排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1281字，纯文字阅读大概需要2分钟。

内容图文

1 归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.mergerSort(nums, 0, len(nums)-1)
        return nums

    def mergerSort(self, nums, left, right):
        if right <= left: return
        mid = (right+left)//2
        self.mergerSort(nums, left, mid)
        self.mergerSort(nums, mid+1, right)
        self.merge(nums, left, mid, right)

    def merge(self, nums, left, mid, right):
        res = []
        i, j = left, mid+1
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                res.append(nums[i])
                i += 1
            else:
                res.append(nums[j])
                j += 1
        while i <= mid:
            res.append(nums[i])
            i += 1
        while j <= right:
            res.append(nums[j])
            j += 1
        #不能写nums = res #注意数组传递！ 变量作用域
        for i in range(len(res)):
            nums[left + i] = res[i]

算法特性

• 时间复杂度（最好）： O ( n l o g n ) O(nlogn) O(nlogn)
• 时间复杂度（最坏）： O ( n l o g n ) O(nlogn) O(nlogn)
• 时间复杂度（平均）： O ( n l o g n ) O(nlogn) O(nlogn)
• 空间复杂度： O ( n ) O(n) O(n)
• 稳定性：稳定

参考资料

十大经典排序算法（动图演示）

内容总结

以上是互联网集市为您收集整理的归并排序（Merge Sort）-- 高级排序算法全部内容，希望文章能够帮你解决归并排序（Merge Sort）-- 高级排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---