归并排序
原题链接:
AC模板源代码:
#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演示
归并排序思路
相关代码解析:
附注:
i与i的区别
i是先赋值,然后再自增;i是先自增,后赋值。
用代码表示就是:
若 a = i++;
则等价于a=i;i=i+1;
而a = ++i;
则等价于 i=i+1;a=i;