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)，是一种稳定的排序算法，适用于大规模数据的排序。掌握归并排序的原理，对于理解分治算法和递归思想非常重要。
