本文主要是介绍【Leetcode每日一题】 分治 - 排序数组（难度⭐⭐）（69)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目解析
题目链接：912. 排序数组
这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。
2.算法原理
归并排序（Merge Sort）是一种采用“分而治之”（Divide and Conquer）策略的高效排序算法。其基本思想是将一个待排序的数组拆分成若干个小的子数组，直到每个子数组只包含一个元素（此时可以认为子数组是有序的），然后再将这些有序的子数组合并成一个大的有序数组，直到合并为最初的数组长度。
算法流程
归并排序的主要流程可以分解为以下两个步骤：
1. 分解（Divide）
- 将待排序的数组从中间位置分成两个大小相近的子数组，直到每个子数组只包含一个元素为止。
- 这个过程是一个递归过程，通过不断地将数组一分为二，实现对待排序数组的分解。
2. 递归合并（Conquer and Combine）
- 从最底层开始，将相邻的两个有序子数组合并成一个新的有序数组，直到合并为最初的数组长度。
- 在合并的过程中，为了保证合并后的数组有序，需要比较两个子数组中的元素，将较小的元素依次放入新的数组中。
算法实现细节
- 递归基准：当子数组的长度为1时，认为该子数组已经有序，无需继续分解。
- 合并操作：合并两个有序子数组时，需要创建一个新的数组来存储合并后的结果。通过比较两个子数组中的元素，将较小的元素依次放入新数组中，直到其中一个子数组的所有元素都被放入新数组。然后将另一个子数组中剩余的元素依次放入新数组，确保合并后的数组有序。
- 空间复杂度：归并排序的空间复杂度为O(n)，其中n为数组的长度。这是因为在合并过程中需要创建一个新的数组来存储合并后的结果。然而，在实际应用中，可以通过一些技巧（如使用原地归并排序）来减少空间复杂度。
- 时间复杂度：归并排序的时间复杂度为O(nlogn)，其中n为数组的长度。这是因为每次递归分解都将数组长度减半，而合并操作的时间复杂度为O(n)。因此，总的时间复杂度为O(nlogn)。
3.代码编写
class Solution {vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;int mid = (right + left) >> 1;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(i = left; i <= right; i++)nums[i] = tmp[i - left];}
};The Last
嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。
觉得有点收获的话，不妨给我点个赞吧！
如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~
这篇关于【Leetcode每日一题】 分治 - 排序数组（难度⭐⭐）（69)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
