912.排序数组（归并排序）

题目

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解法

typedef long long ll;
const int N = 1e5 + 1;
class Solution {ll help[N];void merge(vector<int>& nums, ll l, ll r) {//1、将数组排序if (l >= r) return;ll mid = l + ((r - l) >> 1);ll i = l, j = mid + 1, t = l;while (i <= mid && j <= r) {help[t++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];}//2、将左半区域剩余元素排序while (i <= mid) {help[t++] = nums[i++];}//3、将右半区域剩余元素排序while (j <= r) {help[t++] = nums[j++];}//4、复制数组for (int i = l; i <= r; i++) {nums[i] = help[i];}return;}void mergeSort(vector<int>& nums, ll l, ll r) {if (l < r) {ll mid = l + ((r - l) >> 1);//左边区域mergeSort(nums, l, mid);//右边区域mergeSort(nums, mid + 1, r);//合并左右区域merge(nums, l, r);}}public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();mergeSort(nums, 0, n - 1);return nums;}
};

好的，下面我将详细展示使用归并排序的过程，以数组 nums = {38, 27, 43, 3, 9, 82, 10} 为例。

初始数组

nums = {38, 27, 43, 3, 9, 82, 10}

1. 分解阶段

归并排序首先将数组分解成子数组，直到每个子数组只包含一个元素。

1. 初始分解：

   {38, 27, 43, 3, 9, 82, 10}
   

2. 继续分解：

   {38, 27, 43}  {3, 9, 82, 10}
   

3. 再次分解：

   {38} {27, 43}  {3, 9} {82, 10}
   

4. 继续分解：

   {38} {27} {43}  {3} {9} {82} {10}
   

2. 合并阶段

接下来开始合并和排序：

1. 合并 {27} 和 {43}：

   {27, 43}
   

2. 合并 {27, 43} 和 {38}：

   {27, 38, 43}
   

3. 合并 {3} 和 {9}：

   {3, 9}
   

4. 合并 {82} 和 {10}：

   {10, 82}
   

5. 合并 {3, 9} 和 {10, 82}：

   {3, 9, 10, 82}
   

6. 最后合并 {27, 38, 43} 和 {3, 9, 10, 82}：

   {3, 9, 10, 27, 38, 43, 82}
   

结果

经过归并排序后，数组 nums 最终变为：

nums = {3, 9, 10, 27, 38, 43, 82}

为什么要创建长整型

typedef long long ll;：这行代码为 long long 类型创建了一个别名 ll。这样，在后续的代码中，你可以使用 ll 来代替 long long，使代码更简洁易读。

const int N = 1e5 + 1;：这行代码定义了一个常量 N，其值为 100001。通常在算法中，N 可能用于表示数组的最大大小或某种限制，以确保在使用时不会越界。

在 C++ 中，创建 long long 类型的原因主要是为了处理更大的整数范围。long long 通常用于存储可能超出 int 范围的数值，特别是在涉及到大数运算、数组索引、计数或求和时。以下是一些具体的原因：

1. 数值范围：int 的范围通常是 -2,147,483,648 到 2,147,483,647，而 long long 的范围可以达到 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807，适合处理更大的数值。

2. 避免溢出：在进行大量累加、乘法等运算时，如果使用 int，可能会出现溢出错误。使用 long long 可以降低这种风险。

3. 算法需要：在一些算法（如动态规划、图算法等）中，可能需要处理大量数据或计算结果，使用 long long 确保结果不会溢出。

因此，在需要处理较大整数的情况下，使用 long long 是一种常见的做法。

ll mid = l + ((r - l) >> 1);其中的>>是什么意思

“”>> 是位移运算符，表示右移操作。在这个表达式中，(r - l) >> 1 相当于将 (r - l) 的值除以 2，用于计算中间值 mid，以提高效率。