归并排序（merge_sort）

算法时间复杂度：妥妥的nlogn

步骤：

1.确定分界点  mid = (l+r) >> 1 

2.递归排序左右两边

3.归并——合二为一（用两个指针，分别指向两个序列）

就是递归到最底部，然后对小部分排序，归并为大部分。

代码模板：

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;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    while(i <= mid) tmp[k++] = q[i++]; //补全剩余的
    while(j <= r) tmp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

总的代码：

#include<iostream>
#include<cstdio>
using namespace std;

const int n = 5000000;
int q[n], tmp[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;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main()
{
    int a, t;

    scanf("%d %d", &a, &t);
    for(int i = 0; i < a; i++) scanf("%d", &q[i]);

    merge_sort(q, 0, a-1);

    printf("%d", q[t]);
    system("pause");
    return 0;
}

还发现了一个黑科技， nth_element() 函数

第二个参数是一个指向第 n 个元素的迭代器。如果这个范围内的元素是完全有序的，nth_dement() 的执行会导致第 n 个元素被放置在适当的位置。这个范围内，在第 n 个元素之前的元素都小于第 n 个元素，而且它后面的每个元素都会比它大。算法默认用 < 运算符来生成这个结果, 第 n 个元素之前的元素都小于它，但不必是有序的。同样，第 n 个元素后的元素都大于它，但也不必是有序的。

例如模板题：

第k小的数

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long long q[5000010];

int main()
{
    long long a, t;

    scanf("%lld %lld", &a, &t);
    for(int i = 0; i < a; i++) scanf("%lld", &q[i]);

    nth_element(q, q+t, q+a);

    printf("%lld", q[t]);
    return 0;
}

这个题因为数据有点大，所以用归并与快排都超时了，用这个函数却不会。