本文概述：
- 文章以归并排序为题，向读者介绍了其整体思路、时间复杂度分析、核心代码算法思路，并提供了完整实现代码(C++ & Java)。
样例展示：
创新互联专注于耿马企业网站建设,响应式网站,
商城建设。耿马网站建设公司,为耿马等地区提供建站服务。全流程按需规划网站，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务整体思路：先分治，再合并
算法整体上：
递归的每一层：
数据来源：nums[left,right]，分出的两部分nums[left,mid]，nums[mid + 1,right]
排序操作：遍历两部分，按照大小，将其放入临时数组temp[]，注意下标从0 开始；
放回操作：将排好序的临时数组元素放回本层原数组
遍历的区间的对应关系应为
- nums：
[left,right] - temp：从零开始，因为在每一层的排序时，temp 都是从0 开始的
时间复杂度分析
- 归并是稳定的，在递归排序时，每一趟会将原数组划分为两份，对于N 个数据，总计为
logN层； - 对每一层，均会进行合并(扫描一遍，每一次会扫描
right - left + 1个数)，因此总体为N * logN
核心代码算法思路：一共四步
第一步：确定分界点下标
int mid = (left + right) >>1;
第二步：向下递归，将本层数据以分界点为线，一分为二
merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);
第三步：将由本层分裂出的左右两部分数组按照大小进行合并
- 注意：第二步是递归向下的过程，此时递归深度不断加深，第三步是递归向上，此时为递归回溯操作
//开始合并两个数组
int k = 0,startA = left,startB = mid + 1;
while(startA<= mid && startB<= right)
{if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
else(temp[k++] = nums[startB++]);
}
while(startA<= mid) temp[k++] = nums[startA++];
while(startB<= right) temp[k++] = nums[startB++];
第四步：将本层存放在临时数组中的元素，放回原数组
for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];
代码实现：C++
#include
using namespace std;
const int N = 1e6 + 10;
int n;
int nums[N], temp[N];
void merge_sort(int nums[],int left,int right)
{if(left >= right) return;//递归出口
//本层递归逻辑
int mid = (left + right) >>1;//确定分界点下标
merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);//向下递归
//开始合并两个数组
int k = 0,startA = left,startB = mid + 1;
while(startA<= mid && startB<= right)
{if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
else(temp[k++] = nums[startB++]);
}
while(startA<= mid) temp[k++] = nums[startA++];
while(startB<= right) temp[k++] = nums[startB++];
//将本段区间的有序结果放回原数组
for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];
//for (int i = 0;i< n;i++) nums[i] = temp[i];注意，放回的是本段区间[left,right] 不是整个区间
}
int main()
{scanf("%d",&n);
for(int i = 0;i< n;i++) scanf("%d",&nums[i]);//处理IO
merge_sort(nums,0,n - 1);//进行归并排序
for(int i = 0;i< n;i++) printf("%d ",nums[i]);
}
作者：WAsbry
链接：https://www.acwing.com/activity/content/code/content/353277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码实现：Java
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;
public class MergeSort {
//核心函数：使用归并排序对给定数组的指定区间进行升序排序
public void merge_sort(int[] nums, int left, int right){//递归出口
if (left >= right) return;
//本层递归逻辑
int mid = (left + right) >>1;//选择本层递归数组下标中点作为分界
merge_sort(nums,left,mid);
merge_sort(nums,mid + 1,right);//向下递归
//将本层原数组分裂出的两部分升序合并在临时数组中
int startA = left,startB = mid + 1;//确定两部分起点
ArrayListtemp = new ArrayList<>();//临时集合
while (startA<= mid &&startB<= right){if(nums[startA]< nums[startB]){temp.add(nums[startA++]);
}else {temp.add(nums[startB++]);
}
}
while (startA<= mid){temp.add(nums[startA++]);
}
while (startB<= right){temp.add(nums[startB++]);
}
//将临时数组中的升序序列放回原数组
for(startA = left,startB = 0;startA<= right;startA++,startB++){nums[startA] = temp.get(startB);
}
}
//辅助函数：打印给定数组所有元素
public void printArray(int[] nums){for (int i = 0;i< nums.length;i++){System.out.print(nums[i] + " ");
}
}
//辅助函数：根据键盘输入初始化数组nums,并返回nums;输入：1,2,3;返回nums{1,2,3}
public int[] dealIO(){Scanner sc = new Scanner(new BufferedInputStream(System.in));
String str = sc.next();
String[] strArray = str.split(",");
int[] nums = new int[strArray.length];
for (int i = 0;i< strArray.length;i++){nums[i] = Integer.valueOf(strArray[i]);
}
return nums;
}
public static void main(String[] args) {MergeSort ma = new MergeSort();
int[] nums = ma.dealIO();
ma.merge_sort(nums,0,nums.length - 1);
ma.printArray(nums);
}
}
运行截图：Java
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
名称栏目：算法基础之归并排序-创新互联
标题路径：
http://cdkjz.cn/article/jsegc.html
