分治法的过程
- 划分：将问题分成若干个子问题，这些子问题是同一问题的较小实例。
- 递归求解：通过递归的方法解决子问题。然而，如果子问题的规模足够小，只需以一种直接的方式解决子问题。
- 合并：将子问题的解合并为原问题的解。
合并过程是可选的，有些问题直接递归求解即可
归并排序
通过二分法达到log(n)这样一个层级，然后再通过O(n)的归并操作，就形成了nlog(n)的归并排序
-
二分操作：将n个元素平均分成两部分，再分别将这两部分进行递归二分操作。直到所有分组都只有1个元素（只有一个元素时，数列显然有序）
-
归并操作：从最底层开始逐步合并两个排好序的数列
我这里采用对原数组进行操作，所以先建立一个辅助数组T temp[r-l+1]，通过for循环将原数组数据复制到辅助数组
又因为两个序列都已经有序，因此只需要两个序列的低位轮流进行比较，输的一方为小值，将这个值赋值到原数组，输的一方继续拿出一个值来比较，直到有一方没有元素后，将另一方的所有元素依次赋值到原数组中即可。此时，原数组为两个序列的有序合并。
下面两个子数组分别进行比较，将合适的元素赋值到上面的大数组
#include<bits/stdc++.h>
using namespace std;
//对数组arr[left]-arr[right]进行归并排序
void mergeSort(int arr[],int left,int right ){
//1.划分：进行二分操作
if(left>=right)
return;
int mid=(left+right)/2;
//2.递归
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
//3.合并
//我们要对原数组进行排序，那么复制一个辅助数组
int temp[right-left+1];
for(int i=left;i<=right;i++)
temp[i-left]=arr[i];
//原数组中的左右指针
int curL=left,curR=mid+1;
//arr[k]是原数组中即将要赋值的元素
for(int k=left;k<=right;k++){
//先判断越界
if(curL>mid){//左指针到右边部分，右边的直接赋值即可
arr[k]=temp[curR-left];
curR++;
}else if(curR>right){
arr[k]=temp[curL-left];
curL++;
}else if(temp[curL-left]>temp[curR-left]){//右边的小，右边赋值并且右移1
arr[k]=temp[curR-left];
curR++;
}else if(temp[curL-left]<=temp[curR-left]){
arr[k]=temp[curL-left];
curL++;
}
}
}
int main(){
int x[10005];
int i=0;
int n;
while(cin>>n){
x[i]=n;
i++;
if(cin.get()=='\n')
break;
}
mergeSort(x,0,i-1);
cout<<x[0]<<','<<x[i-1];
return 0;
}