【分治——归并排序】排序数组的归并方法

本文主要是介绍【分治——归并排序】排序数组的归并方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.前言

今天简单展示一个归并排序解题，难度简单。

2.题目简介

题目链接：LINK

3.求解思路

4.示例代码

//归并排序
class Solution {
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}void mergeSort(vector<int>& nums, int begin, int end){if(begin >= end) return;//1.找中间点int mid = (begin + end) >> 1;//此时被划分为了两部分：[begin, mid] [mid+1, end]//2.递归mergeSort(nums, begin, mid);mergeSort(nums, mid + 1, end);//3.回归int cur1 = begin, cur2 = mid + 1, i = begin;while(cur1 <= mid && cur2 <= end){tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= end) tmp[i++] = nums[cur2++];//拷回原来的数组for(int i = 0; i < end - begin + 1; i++){nums[begin + i] = tmp[begin + i];}}
};

---

---

EOF

这篇关于【分治——归并排序】排序数组的归并方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---