归并排序

归并(Merging) ：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n)。

归并思想实例：两堆扑克牌，都已从小到大排好序，要将两堆合并为一堆且要求从小到大排序。

◆ 将两堆最上面的抽出(设为C1，C2)比较大小，将小者置于一边作为新的一堆(不妨设C1 ◆重复上述过程，直到某一堆已抽完，然然后将剩下一堆中的所有牌转移到新堆中。

1 排序思想

① 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；

② 对所有有序子序列进行两两归并，得到én/2ù个长度为2或1的有序子序列――一趟归并；

③ 重复②，直到得到长度为n的有序序列为止。

上述排序过程中，子序列总是两两归并，称为2-路归并排序。其核心是如何将相邻的两个子序列归并成一个子序列。设相邻的两个子序列分别为：

{R[k], R[k+1], …,R[m]}和{R[m+1],R[m+2],…,R[h]}，将它们归并为一个有序的子序列：

{DR[l],DR[l+1],…,DR[m], DR[m+1], …,DR[h] }

2.举例

3.实现代码：

//
//  main.cpp
//  CHelloWorld
//
//  Created by IDEA-MAC03 on 13-12-16.
//  Copyright (c) 2013年 IDEA-MAC03. All rights reserved.
//

#include 
  
   
#include 
   
     #define SIZE 15 //完成一遍合并的函数 void MergeOne(int a[],int b[],int n,int len) { int i,j,k,s,e; s = 0; while (s + len < n) { e = s+ 2*len -1; if (e >= n) { e = n-1; } //相邻有序合并 k = s; i = s; j = s + len; while (i < s+len && j<= e) { if (a[i]<= a[j]) { b[k++] = a[i++]; } else { b[k++] = a[j++]; } } while (i < s+len) { b[k++] = a[i++]; } while (j<= e) { b[k++] = a[j++]; } s = e + 1; } if (s
    
     
 
     
运行结果：
 
     

 
 
     
 
 
 
     

 
 
     
参考书籍:《C/C++常用算法手册》 《数据结构-清华大学严蔚敏》