转载

《算法导论》读书笔记之排序算法—Merge Sort 归并排序算法

自从打ACM以来也算是用归并排序了好久，现在就写一篇博客来介绍一下这个算法吧 :)

图片来自维基百科，显示了完整的归并排序过程。例如数组{38, 27, 43, 3, 9, 82, 10}.

在算法导论讲分治算法一章的时候提到了归并排序。首先，归并排序是一个分治算法。

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，

即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。

merg() 函数是用来合并两个已有序的数组. 是整个算法的关键。

那么归并排序有什么用处呢？

对数组中元素经行排序
对链表中元素经行排序，其它排序算法如堆排序和快速排序不能对链表排序（参考我写的博客http://www.cnblogs.com/wushuaiyi/p/4558391.html）
可以求逆序数（参考我写的博客http://www.cnblogs.com/wushuaiyi/p/4362149.html）
外排序

下面是我写的归并排序使用C++实现的一个版本：

#include <iostream> using namespace std; const int MAXN = 10900; int a[MAXN], tmp[MAXN], n; void Merge (int l, int m, int r) {  int i = l;  int j = m + 1;  int k = l;  while (i <= m && j <= r) {   if (a[i] < a[j]) {    tmp[k++] = a[i++];   } else {    tmp[k++] = a[j++];   }  }  while (i <= m) {   tmp[k++] = a[i++];  }  while (j <= r) {   tmp[k++] = a[j++];  }  for (int i = l; i <= r; ++i)   a[i] = tmp[i]; } void Merge_sort (int l, int r) {  if (l < r) {   int m = (l + r) >> 1;   Merge_sort (l, m);   Merge_sort (m + 1, r);   Merge (l, m, r);  } } int main() {  std::ios::sync_with_stdio(false);  int i, j, t, k, u, c, v, p, numCase = 0;  while (cin >> n) {   for (i = 0; i < n; ++i) {    cin >> a[i];   }   Merge_sort(0, n - 1);   for (i = 0; i < n; ++i) {    cout << a[i] << endl;   }  }  return 0; }