分治算法

分治法的过程

1. 划分：将问题分成若干个子问题，这些子问题是同一问题的较小实例。
   
2. 递归求解：通过递归的方法解决子问题。然而，如果子问题的规模足够小，只需以一种直接的方式解决子问题。
   
3. 合并：将子问题的解合并为原问题的解。
   

合并过程是可选的，有些问题直接递归求解即可

归并排序

通过二分法达到log(n)这样一个层级，然后再通过O(n)的归并操作，就形成了nlog(n)的归并排序

1. 二分操作：将n个元素平均分成两部分，再分别将这两部分进行递归二分操作。直到所有分组都只有1个元素（只有一个元素时，数列显然有序）
   
   
2. 归并操作：从最底层开始逐步合并两个排好序的数列
   我这里采用对原数组进行操作，所以先建立一个辅助数组T temp[r-l+1]，通过for循环将原数组数据复制到辅助数组
   又因为两个序列都已经有序，因此只需要两个序列的低位轮流进行比较，输的一方为小值，将这个值赋值到原数组，输的一方继续拿出一个值来比较，直到有一方没有元素后，将另一方的所有元素依次赋值到原数组中即可。此时，原数组为两个序列的有序合并。
   

下面两个子数组分别进行比较，将合适的元素赋值到上面的大数组

#include<bits/stdc++.h>

usingnamespacestd;

//对数组arr[left]-arr[right]进行归并排序

voidmergeSort(intarr[],intleft,intright ){

   //1.划分：进行二分操作

   if(left>=right)

       return;

   intmid=(left+right)/2;

   //2.递归

   mergeSort(arr,left,mid);

   mergeSort(arr,mid+1,right);

   //3.合并

   //我们要对原数组进行排序，那么复制一个辅助数组

   inttemp[right-left+1];

   for(inti=left;i<=right;i++)

       temp[i-left]=arr[i];

   //原数组中的左右指针

   intcurL=left,curR=mid+1;

   //arr[k]是原数组中即将要赋值的元素

   for(intk=left;k<=right;k++){

       //先判断越界

       if(curL>mid){//左指针到右边部分，右边的直接赋值即可

           arr[k]=temp[curR-left];

           curR++;

       }elseif(curR>right){

           arr[k]=temp[curL-left];

           curL++;

       }elseif(temp[curL-left]>temp[curR-left]){//右边的小，右边赋值并且右移1

           arr[k]=temp[curR-left];

           curR++;

       }elseif(temp[curL-left]<=temp[curR-left]){

           arr[k]=temp[curL-left];

           curL++;

       }

   }

}

intmain(){

   intx[10005];

   inti=0;

   intn;

   while(cin>>n){

       x[i]=n;

       i++;

       if(cin.get()=='\n')

           break;

   }

   mergeSort(x,0,i-1);

   cout<<x[0]<<','<<x[i-1];

   return0;

}