归并排序算法

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

思路：

l，r分别为闭区间的左右边界，tem[]为临时数组，mid为中间值，将整数组分为左右两个子数组分别递归处理左右两个数组，使其成为有序数组i，j分别指向子数组的起点，比较其指向数的大小，将小的数存入临时数组中将左右两个数组未循环完的数直接接到临时数组中将临时数组中的数存回q[]数组中 题目：

#include
using namespace std;
const int N=1e5+10;
int n;
int q[N],tem[N];

void merge_sort(int q[],int l, int r){
    if(l>=r)return ;
    int mid=(l+r)>>1;

    //分别递归处理左右两个数组，使其成为有序数组

    merge_sort(q,l,mid),merge_sort(q,mid+1,r); 

    //将小的数存入临时数组中

    int k=0,i=l,j=mid+1;    //i，j分别指向子数组的起点
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])tem[k++]=q[i++];
        else tem[k++]=q[j++];
    }

    //将左右两个数组未循环完的数直接接到临时数组中

    while(i<=mid)tem[k++]=q[i++];
    while(j<=r)tem[k++]=q[j++];

    //将临时数组中的数存回q[]数组中

    for(i=l,j=0;i<=r;)q[i++]=tem[j++];
}

int main(){
    cin>>n;
    for(int i=0;i>q[i];
    merge_sort(q,0,n-1);
    for(int i=0;i 
 有关算法竞赛的题目会继续更新，欢迎评论交流！