归并排序

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

图像解释

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

• 初始状态：6,202,100,301,38,8,1
• 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
• 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
• 第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
• 总的比较次数为：3+4+4=11；
• 逆序数为14；

实现

• python

  numn = 0
  def MergeSort(lists):
  	if len(lists) <= 1:
  		return lists
  	num = int( len(lists) / 2 )
  	left = MergeSort(lists[:num])
  	right = MergeSort(lists[num:])
  	return Merge(left, right)
  def Merge(left,right):
  	r, l=0, 0
  	num=0
  	global numn
  	result=[]
  	while l<len(left) and r<len(right):
  		if left[l] <= right[r]:
  			result.append(left[l])
  			l += 1
  		else:
  			num +=len(left)-l
  			result.append(right[r])
  			r += 1
  	result += list(left[l:])
  	result += list(right[r:])
  	numn += num
  	return result
  
  print (MergeSort([1,3,6,9,0,8,5,7,4,2]))
  print(numn)
  

• c++

  //归并排序及求逆序对
  #include<bits/stdc++.h>
  using namespace std;
  #define N 1000005
  int a[N] ,b[N];//b为辅助数组
  long long cnt;
  void merge_sort(int l , int r)
  {
  	if(r-l > 0)//如果整个区间中元素个数大于1，则继续分割
  	{
  		int mid = (l+r) / 2 ;
  		int i = l; //辅助数组的下标
  		int p = l , q = mid+1;
  		merge_sort(l , mid);
  		merge_sort(mid+1 , r);
  		//printf("%d-%d %d-%d\n",p,mid ,q ,r);
  		while(p<=mid || q<=r)//左右两部分只要有一部分不为空
  		{
  			if(q>r || (p<=mid && a[p]<=a[q]))//从左半数组复制到辅助数组
  				b[i++] = a[p++];
  			else
  			{
  				b[i++] = a[q++];
  				cnt += mid -p +1;//将逆序对的个数累加起来
  			}
  		}
  		for(i = l ; i <= r; i++)//将b中排好序的元素复制到a中
  			a[i] = b[i];
  	}
  }
  int main()
  {
  	int n;
  	while(cin >> n)
  	{
  		for(int i = 1 ; i <= n; i ++)
  			cin >> a[i];
  		cnt = 0;
  		merge_sort(1 , n);
  		for(int i = 1; i <= n; i++)
  			cout << a[i] << " ";
  		cout << endl;
  		cout << "逆序对有：" << cnt <<endl;
  	}
  	return 0;
  }
  

归并排序

原文：https://www.cnblogs.com/flandre2333/p/13576843.html