复杂度: O(nlogn)
一种稳定的排序算法, 分治思想
- #include<bits/stdc++.h>
- using namespace std;
- int a[500],t[500];
- void merge(int l,int r){
- if(l == r) return;
- int mid = (l+r)/2;
- merge(l,mid);
- merge(mid+1,r);
- int i = l,j = mid+1,k = l;
- while(i<=mid&&j<=r){
- if(a[i] <= a[j]){
- t[k++] = a[i++];
- }else{
- t[k++] = a[j++];
- }
- }
- while(i<=mid) t[k++] = a[i++];
- while(j<=r) t[k++] = a[j++];
- for(int i=l;i<=r; i++){
- a[i] = t[i];
- }
- }
- int main(){
- int n;
- cin>> n;
- for(int i=1; i<=n; i++){
- cin>> a[i];
- }
- merge(1,n);
- for(int i=1; i<=n; i++){
- cout << a[i] << " ";
- }
- return 0;
- }
求逆序对: 洛谷 P1908 https://www.luogu.com.cn/problem/P1908
归并排序
来源: http://www.bubuko.com/infodetail-3438815.html