归并排序——模板题

原题链接:

ACwing归并排序模板题

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
#include <iostream>

using namespace std;

const int N = 100010;

int a[N];
int tmp[N];

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

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

int k = 0 , i = l , j = mid + 1;
while ( i <= mid && j <= r)
if (a[i] < a[j] ) tmp[k++] = a[i++];
else tmp[k++] = a[j++];

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

int main()
{
int n ;
cin >> n;
for (int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);
merge_sort( a , 0 , n - 1);

for (int i = 0 ; i < n ; i ++) printf("%d ",a[i]);

return 0;
}

归并排序算法原理:

归并排序GIF演示

3.gif

归并排序思路

image-20210204125013961


相关代码解析:

image-20210204130152524


附注:

i++与++i的区别

i++是先赋值,然后再自增;++i是先自增,后赋值。
用代码表示就是:
a = i++;则等价于a=i;i=i+1;
a = ++i;则等价于 i=i+1;a=i;


参考资料:

  1. YXC讲解视频
  2. i++与++i区别