LeetCode 归并排序 题解

张开发
• 2026/4/18 2:09:28 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode 归并排序 题解
LeetCode 归并排序 题解题目描述实现归并排序算法对一个整数数组进行排序。示例 1输入nums [5,2,3,1] 输出[1,2,3,5]示例 2输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]解题思路方法归并排序思路归并排序是一种分治算法它的工作原理是将数组分成两半对每一半进行排序然后将排序好的两半合并成一个有序数组。归并排序的过程是递归的它不断地将数组分成更小的子数组直到子数组的长度为 1然后开始合并。复杂度分析时间复杂度O(n log n)其中 n 是数组的长度。无论输入数据如何时间复杂度都是 O(n log n)。空间复杂度O(n)需要使用额外的空间来存储合并过程中的临时数组。代码实现方法归并排序def merge_sort(nums): # 递归终止条件数组长度小于等于 1 if len(nums) 1: return nums # 计算中间位置 mid len(nums) // 2 # 递归排序左半部分 left merge_sort(nums[:mid]) # 递归排序右半部分 right merge_sort(nums[mid:]) # 合并两个有序数组 return merge(left, right) def merge(left, right): # 初始化结果数组和指针 result [] i j 0 # 合并两个有序数组 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 将剩余元素添加到结果数组 result.extend(left[i:]) result.extend(right[j:]) return result # 测试 nums1 [5,2,3,1] print(merge_sort(nums1)) # 输出[1,2,3,5] nums2 [5,1,1,2,0,0] print(merge_sort(nums2)) # 输出[0,0,1,1,2,5]测试用例测试用例 1输入nums [5,2,3,1]输出[1,2,3,5]测试用例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]总结本题是排序算法的经典问题主要考察对归并排序算法的理解和实现。归并排序是一种分治算法它通过将数组分成两半对每一半进行排序然后合并排序好的两半来完成排序。归并排序的核心思想是将数组递归地分成更小的子数组直到子数组的长度为 1然后开始合并每次合并两个有序数组。这种方法的时间复杂度为 O(n log n)是一种稳定的排序算法适用于大规模数据的排序。掌握归并排序的原理对于理解分治算法和递归思想非常重要。

更多文章