归并排序

,
你以为有个sort就可以为所欲为？！

简介

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

约翰·冯·诺伊曼
时间复杂度$O(n \log n) $

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;

void My_merge(int arr[], int l, int mid, int r)
{
    int aux[r - l + 1];
    for (int m = l; m <= r; m++)
    {
        aux[m - l] = arr[m];
    }

    int i = l, j = mid + 1;

    for (int k = l; k <= r; k++)
    {
        if (i > mid)
        {
            arr[k] = aux[j - l];
            j++;
        }
        else if (j > r)
        {
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l])
        {
            arr[k] = aux[i - l];
            i++;
        }
        else
        {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

void merge_sort(int arr[], int l, int r)
{
    if (l >= r)
        return ;
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    My_merge(arr, l, mid, r);
}

//void mergesort(int arr[],int n)//迭代
//{
//    for(int sz=1;sz<=n;sz+=sz)
//    {
//        for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界
//        {//对arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
//            My_merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函数防止越界
//        }
//    }
//}

void My_merge_sort(int arr[], int n)//duoyu
{
    merge_sort(arr, 0, n - 1);
}

int t, n;
int main()
{
    int a[10] = {3, 1, 4, 5, 6, 7, 8, 9, 2, 10};
    My_merge_sort(a, 10);
    for (int i = 0; i < 10; i++)
        cout << a[i] << ' ';
    puts("");
    return 0;
}

Minimum Inversion Number

一道很厉害的题，可以用三种方法来写

1.线段树

原理

因为题目输入是从零到n-1的，所以可以引入线段树思想，将每次一个数的输入前就行一次区间查询，就可以得到该数对应的逆序数，然后再单点更新即可

AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: 我也借鉴了好多线段树+lazy的模板，维护值有用数组和结构体的，个人比较喜欢用结构体储存
 然后线段树的操作也就那几种(虽然叫法各异，但是实际上是一样的)：
 建树：build
 更新：update，change，add
 查询：find，query
 标记下放：pushdown
 向上更新：pushup(这个函数就一行，感觉没有必要，即两个子节点向上更新父节点的维护值)
 注意：无论是线段树还是树状数组，初始数组都应该从1开始存数据
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;

ll a[maxn];
struct node
{
    ll sum;
    ll lazy;
} A[maxn << 2];

void build(int u, int l, int r)
{
    A[u].lazy = 0;
    if (l == r)
    {
        A[u].sum = 0;//这里可以改为初始数组的
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    A[u].sum = A[2 * u].sum + A[2 * u + 1].sum;//等价pushup操作
}

//下放操作，将当前的lazy下放
void pushdown(int u, int l,int  r)
{
    if (A[u].lazy == 0)
        return ;
    int mid = (l + r) / 2;
    A[u * 2].sum += A[u].lazy * (mid - l + 1);
    A[u * 2 + 1].sum += A[u].lazy * (r - mid);
    A[u * 2].lazy += A[u].lazy;
    A[u * 2 + 1].lazy += A[u].lazy;
    A[u].lazy = 0;
}

//l,r表示更新区间sl,sr一开始为1, n, u == 1

void add(int u, int sl, int sr, int l, int r, ll k)
{
    if (l > sr || r < sl)
        return ;
    if (l <= sl && r >= sr)
    {
        A[u].sum += k * (sr - sl + 1);
        A[u].lazy += k;
        return ;
    }
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    add(2 * u, sl, mid, l, r, k);
    add(2 * u + 1, mid + 1, sr, l, r, k);
    A[u].sum = A[u * 2].sum + A[u * 2 + 1].sum;
    return ;
}

ll query(int u, int sl, int sr, int l, int r)
{
    if (l > sr || r < sl)
        return 0;
    if (l <= sl && r >= sr)
        return A[u].sum;
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    return (query(2 * u, sl, mid, l, r) + query(2 * u + 1, mid + 1, sr, l, r));
}

int t, n, q, x, y, k;
char c;
int main()
{
//    ios::sync_with_stdio(false);
    while (~scanf("%d", &n))
    {
        build(1, 1, n - 1);
        ll temp = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            temp += query(1, 1, n - 1, a[i], n - 1);
            add(1, 1, n - 1, a[i], a[i], 1);
        }
//        cout << temp << endl;
        int ans = temp, sum = temp;
        for (int i = 1; i <= n - 1; i++)
        {
            sum = sum - a[i] + (n - 1 - a[i]);
            ans = min(ans, sum);
        }
        printf ("%d\n", ans);
    }

//注意：无论是线段树还是树状数组，初始数组都应该从1开始存数据


    return 0;
}
//78MS	1468K

2.树状数组

原理同线段树
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<string>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int eps=1e-10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn=100005 * 4;
class TA
{
private:
    int e[maxn];
    int len = maxn;
    int lowbit(int k)
    {
        return k & (-k);
    }
public:
    void add(int x,int v)													//单点更新
    {
        while(x <= len)
            e[x] += v,x += lowbit(x);
    }
    void init(int* getin,int _len)											//初始化
    {
        len = _len;
        for(int i = 1; i <= len; i ++)
            add(i,*(getin + i - 1));
    }
    void init_0()
    {
        len = maxn,memset(e, 0, sizeof(e));
    }
    int getsum(int x)														//询问
    {
        int sum = 0;
        while(x > 0)
            sum += e[x],x -= lowbit(x);
        return sum;
    }
    void range_add(int l, int r, int x)  //给区间[l, r]加上x
    {
        add(l, x), add(r + 1, -x);
    }
    int range_ask(int l, int r)  //区间求和
    {
        return getsum(r) - getsum(l - 1);
    }
} ta;

int a[maxn],n,m;//区间查询，单点修改
int main()
{
    while (~scanf("%d",&n))
    {
        int ans = 0, sum = 0;
        ta.init_0();
        for (int i = 1;i <= n; i++)
        {
            scanf("%d", &a[i]);
            ans += ta.range_ask(a[i] + 1, n);
            ta.add(a[i] + 1, 1);
        }

        sum = ans;
        for (int i = 1; i <= n - 1; i++)
        {
            sum = sum - 2 * a[i] + n - 1;
            ans = min(ans , sum);
        }
        printf("%d\n", ans);
    }
    return 0;
}
//78MS	2940K

3.merge-sort求逆序数

原理

引用一波

在《白话经典算法系列之五归并排序的实现》中观察归并排序——合并数列(1，3，5)与(2，4)的时候：
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;

int count1 = 0;//归并排序求逆序数的

void My_merge(int arr[], int l, int mid, int r)
{
    int aux[r - l + 1];
    for (int m = l; m <= r; m++)
    {
        aux[m - l] = arr[m];
    }

    int i = l, j = mid + 1;

    for (int k = l; k <= r; k++)
    {
        if (i > mid)
        {
            arr[k] = aux[j - l];
            j++;
        }
        else if (j > r)
        {
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l])
        {
            arr[k] = aux[i - l];
            i++;
        }
        else
        {
            arr[k] = aux[j - l];
            j++;
            count1 += (mid - i + 1);//emm
        }
    }
}

void merge_sort(int arr[], int l, int r)
{
    if (l >= r)
        return ;
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    My_merge(arr, l, mid, r);
}

//void mergesort(int arr[],int n)//迭代
//{
//    for(int sz=1;sz<=n;sz+=sz)
//    {
//        for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界
//        {//对arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
//            My_merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函数防止越界
//        }
//    }
//}

void My_merge_sort(int arr[], int n)//duoyu
{
    merge_sort(arr, 0, n - 1);
}

int t, n, a[maxn], x[maxn];
int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            x[i] = a[i];
        }

        count1 = 0;
        My_merge_sort(x, n);
        int ans = count1, sum = count1;
        for (int i = 0; i < n - 1; i++)
        {
            sum = sum - 2 * a[i] + n - 1;
            ans = min(ans, sum);
        }
        printf("%d\n", ans);
    }
    return 0;
}
//46MS	1388K用时是真的短！

参考资料

大佬博客
巨巨博客