归并排序(merge_sort)

数据与算法之美 2020-07-05

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

步骤:

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

2.递归排序左右两边

3.归并——合二为一(用两个指针,分别指向两个序列)

归并排序(merge_sort)就是递归到最底部,然后对小部分排序,归并为大部分。

代码模板:

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;
}

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

相关推荐