许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关地若干子问题。这些算法典型的遵循分治法地思想：将原问题分解成几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

• 分解原问题为若干子问题，这些子问题是原问题规模较小的实例。
• 解决这些子问题，递归地求解各子问题。若子问题规模足够小，则直接求解。
• 合并这些子问题的解成原问题的解。

归并排序：完全遵循分治模式。

• 分解：分解该待排序的n个元素的序列成各具n/2元素的两个子序列。
• 解决：使用归并排序递归地解决两个子序列。
• 合并：合并两个已排序的子序列以产生以排序的答案。

归并排序示意图：

归并排序实现：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN = 1e5;
int a[MAXN], T[MAXN];
void merge_sort(int* A, int x, int y, int* T);
int main() 
{int n;cin>>n;for (int i = 0; i < n; i++) {cin >> a[i];}merge_sort(a, 0, n, T);for (int i = 0; i < n; i++) {cout << a[i] << endl;}return 0;
}void merge_sort(int* A, int x, int y, int* T) 
{if (y - x > 1) {int m = x + (y - x) / 2;int p = x, q = m, i = x;merge_sort(A, x, m, T);merge_sort(A, m, y, T);while (p < m || q < y) {if (q >= y || (p < m && A[p] <= A[q])) {T[i++] = A[p++];} else {T[i++] = A[q++];}}for (int i = x; i < y; i++) {A[i] = T[i];}}
}

例题1:

Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.

Merge(A, left, mid, right)n1 = mid - left;n2 = right - mid;create array L[0...n1], R[0...n2]for i = 0 to n1-1do L[i] = A[left + i]for i = 0 to n2-1do R[i] = A[mid + i]L[n1] = SENTINELR[n2] = SENTINELi = 0;j = 0;for k = left to right-1if L[i] <= R[j]then A[k] = L[i]i = i + 1else A[k] = R[j]j = j + 1Merge-Sort(A, left, right){if left+1 < rightthen mid = (left + right)/2;call Merge-Sort(A, left, mid)call Merge-Sort(A, mid, right)call Merge(A, left, mid, right)

Input

In the first line n is given. In the second line, n integers are given.

Output

In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Constraints

• n ≤ 500000
• 0 ≤ an element in S ≤ 109

Sample Input 1

10
8 5 9 2 6 3 7 1 10 4

Sample Output 1

1 2 3 4 5 6 7 8 9 10
34

Mem （MB）：6.5

#include <stdio.h>
#include <stdlib.h>
const int maxn = 500000 + 100;
int a[maxn],T[maxn];
int count=0;
void merge_sort(int *A,int x,int y,int *T);
int main ()
{int n,i;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);merge_sort(a,0,n,T);for(i=0;i<n;i++){if(i!=n-1)printf("%d ",a[i]);elseprintf("%d\n",a[i]);}printf("%d\n",count);}return 0;
}
void merge_sort(int *A,int x,int y,int *T)
{if(y-x>1){int mid=x+(y-x)/2;int p=x,q=mid,i=x;merge_sort(A,x,mid,T);merge_sort(A,mid,y,T);while(p<mid || q<y){if(q>=y || (p<mid && A[p]<=A[q])){count++;T[i++]=A[p++];}else{count++;T[i++]=A[q++];}}for(i=x;i<y;i++){A[i]=T[i];}}
}

Mem （MB）：7

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int maxn = 500000;
const int  INF = 0x3f3f3f3f;
int a[maxn],L[maxn/2+2],R[maxn/2+2];
int count;
void merge(int array[],int p,int q,int r)
{int n1=q-p,n2=r-q,i,j,k;for(i=0;i<n1;i++){L[i]=array[p+i];}L[n1]=INF;R[0]=-1;for(j=0;j<n2;j++){R[j]=array[q+j]; }R[n2]=INF;i=0;j=0;for(k=p;k<r;k++){if(L[i]<=R[j]){count++;array[k]=L[i++];}else{count++;array[k]=R[j++];}}
}void merge_sort(int array[],int p,int r)
{if(p+1<r){int q=(p+r)/2;merge_sort(array,p,q);merge_sort(array,q,r);merge(array,p,q,r);		}
}int main ()
{int len,i;while(scanf("%d",&len)!=EOF){count=0; for(i=0;i<len;i++){scanf("%d",&a[i]);}merge_sort(a,0,len);for(int i=0;i<len;i++){if(i!=len-1)printf("%d ",a[i]);elseprintf("%d\n",a[i]);}printf("%d\n",count);		}return 0;
} 

例题2：

POJ 2299

求逆序对

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入
第一行是一个整数n，表示该排列有n个数（0<=n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。输出输出该排列的逆序数
例如：输入：6          2 6 3 4 5 1输出：8

基本思路：

1.使用二分归并排序法【分治法】进行求解；

2.将序列依此划分为两两相等的子序列；

3.对每个子序列进行排序（比较r[i]>r[j],如果满足条件，则求该子序列的逆序数count=m-i+1,其中m=(start+end)/2）

4.接着合并子序列即可。

#include <stdio.h>
#include <stdlib.h>
const int maxn = 500000+100;
long long count;
int  a[maxn],r1[maxn];/*合并子序列*/
void Merge(int s,int m,int t)
{int i=s,j=m+1,k=s;while(i<=m && j<=t){if(a[i]<=a[j])r1[k++]=a[i++];else{r1[k++]=a[j++];count+=(m-i+1);}}while(i<=m)r1[k++]=a[i++];while(j<=t)r1[k++]=a[j++];for(i=s;i<=t;i++)a[i]=r1[i];
} /*对序列r[s]-r[t]进行归并排序*/ 
void MergeSort(int s,int t)
{int m;if(s==t) return;else{m=(s+t)/2;MergeSort(s,m);MergeSort(m+1,t);Merge(s,m,t);}
}int main()
{int n,i;while(scanf("%d",&n)!=EOF && n){count=0;for(i=0;i<n;i++)scanf("%d",&a[i]);MergeSort(0,n-1);printf("%lld\n",count);}return 0;
}