当前位置：
> > 查看文章
归并排序（递归实现）- 数据结构和算法94
归并排序（递归实现）
让编程改变世界
Change the world by program
归并排序（递归实现）
“归并”一词在中文含义中就是合并的意思，而在数据结构中的定义是将两个或者两个以上的有序表组合成一个新的有序表，就叫归并。
归并排序（Merge Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到?n/2?个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
好了，那么有了指导方针，代码就容易多了，相信大家跟着小甲鱼的数据结构和算法这个系列课程折腾了这么久，代码上的功夫应该有了很大的长进，自己不妨先尝试一下哈，这里我们使用递归来实现：
…… 省略，具体请看视频讲解 ……
小甲鱼在干啥
如果您觉得小甲鱼的视频能够给您带来知识和快乐，您可以选择赞助我们，让我们可以持续为您推出更多精彩的原创编程教学^_^
手机用户打开支付宝钱包，扫描下方支付宝二维码即可：
电脑用户点击下方按钮即可跳转至支付宝转账页面：
感谢您对我们发展的支持和认可！
更多新鲜事儿
加载中……> 博客详情
摘要: 本文对二路归并排序进行极简介绍，并给出C下递归和非递归两个版本代码。
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 其对数组进行排序时的基本操作在于两个有序序列进行合并操作。其代码部分在后面给出。 而进行整体数组排序时，可先将n个元素看作n个有序序列，对其两两进行合并，于是结果成为floor(n/2)个有序序列，再将其进行两两合并。直到最终合并成为一个整体有序序列。
后面给出的算法包含两个版本。一个是递归方法，另一个是非递归方法。其中递归方法是分治法的典型应用。
#include&iostream&
void dispList(int raw[], int n){
//打印数组
//from 1 to n not 0 to n
for (int i = 1; i &= i++) cout && raw[i] && ' ';
void mergeSort(int raw[], int n){
//merge with no recursion非递归方法
int *temp = new int[n + 1]; //由于合并操作的辅助空间需要对等的长度
for (int i = 1; i & i = i * 2){//两两归并，直到归并的长度大于序列长度跳出
int right_a, right_b, left_a, left_b; //每次比较[left_a...left_b-1]; [right_a...right_b-1]
int cursor = 1;//记录相对位置，每进行一趟归并将其重新置为1
for (left_a = 1; left_a &= n - left_a = right_b){
left_b = right_a = left_a +
right_b = right_a +
if (right_b&n + 1) right_b = n + 1;//如果甩下一个尾巴不够i长度，那么直接将right_b置n+1;
//如下格式是经典的合并三段while语句
while (left_a & left_b && right_a&right_b)
temp[cursor++] = (raw[left_a]&raw[right_a]) ? (raw[left_a++]) : (raw[right_a++]);
while (left_a & left_b)
temp[cursor++] = raw[left_a++];
while (right_a & right_b)
temp[cursor++] = raw[right_a++];
//将辅助空间写入原始序列.
while ((--cursor) != 0)
raw[cursor] = temp[cursor];
//以下给出递归方法，注意体会分治思想。
void merge_joint(int raw[], int temp[], int start, int middle, int end){
&& &//每次meger raw[start...middle-1] and raw[middle...end]
&& &int cursor_l = start, cursor_r =
&& &int cursor =
&& &//同样，三段经典while合并语句
&& &while (cursor_l & middle && cursor_r &= end)
&& &&& &temp[cursor++] = (raw[cursor_l] & raw[cursor_r]) ? raw[cursor_l++] : raw[cursor_r++];
&& &while (cursor_l & middle)
&& &&& &temp[cursor++] = raw[cursor_l++];
&& &while (cursor_r &= end)
&& &&& &temp[cursor++] = raw[cursor_r++];
&& &while ((--cursor) &= start)
&& &&& &raw[cursor] = temp[cursor];//合并好后写入原始序列
void merge_R(int raw[], int temp[], int n, int start, int end){
&& &if (start == end)
&& &&& &int mid = (start + end) / 2;
&& &&& &//先合并左面，再合并右边，最后合并整体
&& &&& &merge_R(raw, temp, n, start, mid);&& &
&& &&& &merge_R(raw, temp, n, mid + 1, end);
&& &&& &merge_joint(raw, temp, start, mid + 1, end);
void mergeSortRe(int raw[], int n){
&& &//最后调用归并排序
&& &int *temp = new int[n + 1];
&& &merge_R(raw, temp, n, 1, n);//需要传入辅助空间
&& &delete []
void main(){
&& &int a[9] = { 0, 3, 4, 8, 6, 7, 23, 21, 18 };
&& &mergeSortRe(a, 8);
&& &dispList(a, 8);
复杂度分析
一趟归并调用对长度为
子序列的两两合并操作。其次数约为
一直到最后，需要进行的排序趟数为:
结合两种操作，最后其时间复杂度为O(nlogn). 由于合并操作需要等长辅助空间，所以空间复杂度为O(n)
复杂度为O(nlogn) 需要等长辅助空间 相比于快排和堆排序，它是一种稳定排序 归并排序在实际应用中较少作为内部排序。递归方式调用实用性差。
支付宝支付
微信扫码支付
打赏金额: ￥
已支付成功
打赏金额: ￥为什么使用归并排序？
java中的Arrays.sort(Object[] o)是对数组进行排序，它使用的是归并排序的方式，
快速排序要比归并排序更快一些，但为什么使用归并排序了？原因是归并排序是一种稳定的排序
方式，即归并排序不交换相同的元素，这就意味着，在按一种方式排序后同时可以按另外一种
方式进行排序。比如员工可以首先按工资排序，然后按名字排序，一种排序不会打乱另一种排序
的顺序。
下面分析下sort方法的简化版：
* 归并排序 (递归实现)
* 前提： 每个元素要有可比性，这里元素必须实现Comparable接口。
* 基本原理为：1.拆分 假设有N个元素的列表，首先把它拆分成2个或2个
* 以上的元素组成的新的列表(这里我的新列表长度不超过3)，分别对对它们进行排序。
* 2.归并。把所有的排好序的子类表两两归并，如此重复，直到归并成一个含N个
* 元素的有序列表为止
* 图解：(大于3就继续分解)
* @param src 临时中间数组，它是目标数组的拷贝
* @param target 目标排序数组
* @param low 需排序的起始索引
* @param high 需排序的结束索引
public static void mergeSort(Object[] src,Object[] dest,int low,int high){
int length = high -
if(length & 3 ){ //对长度小于3的列表排序
//排序方法一：起泡排序(大数沉底)
for(int i=i&high-1;i++){
for(int j=j&high-1-i+j++){
if(((Comparable) dest[j]).compareTo(dest[j+1]) & 0){
swap(dest, j, j+1);
//排序方法二：这是起泡排序的一种变体（小数上浮）
for (int i = i & i++){
for (int j = j & j--){
if(((Comparable) dest[j - 1]).compareTo(dest[j]) & 0){
swap(dest, j-1, j);
int mid = (high + low)/2; //拆分
mergeSort(dest, src, low, mid);
//递归，可能会继续拆分(那么必然继续合并)
mergeSort(dest, src, mid, high);
//开始归并,方法一
for(int i=low,p=low,q=i&i++){
//第一个条件时为了添加剩余的值
if(q &= high || (p & mid &&((Comparable) src[p]).compareTo(src[q]) &= 0)){
dest[i] = src[p++];
dest[i] = src[q++];
//开始归并，方法二
int p = //第一个列表指针
//第二个列表指针
while(p & mid && q &high){
if(((Comparable) src[p]).compareTo(src[q]) &= 0){
dest[i++] = src[p++];
dest[i++] = src[q++];
//添加剩余的值
while(p & mid && i&high){
dest[i++] = src[p++];
while(q & high && i&high){
dest[i++] = src[q++];
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
递归形式的算法在形式上比较简洁，但实用性不够好。
下面讲讲归并排序的非递归实现
public class MergeDemo{
public static void main(String[] args) {
String[] a= {"9","8","7","6","5","4","3","2","1"};
Object[] aux = (Object[])a.clone();
mergeSort(aux, a);
for(int i=0;i&a.i++){
System.out.println(a[i]);
//每个拆分的列表元素个数&=3
private static final int INSERTIONSORT_THRESHOLD = 3;
* 归并排序(非递归实现)
public static void mergeSort(Object[] src,Object[] dest){
int spreCount = INSERTIONSORT_THRESHOLD;
int low,mid,
int len = src.
if(len &= INSERTIONSORT_THRESHOLD*2){
//如果只能划分为两组，直接排序
sort(dest,0,len);
while(spreCount & len){
for(int i=0;i&i=high){ //依次排序归并相邻两个列表
high = low + spreCount * 2 ;
mid = low + spreC
if(high &= len){
int l = high -
if(l &= INSERTIONSORT_THRESHOLD){
sort(src,low,high);
if(spreCount == 3){
//所有拆分的列表只进行一次排序
sort(dest,low,mid);
sort(dest,mid,high);
if(l == len) //最后一次归并把src有次序的赋给dest
Merge(src,dest,low,mid,high);
Merge(dest,src,low,mid,high);
spreCount *= 2;
//对拆分的每个列表进行排序
private static void sort(Object[] dest,int low,int high){
for (int i = i & i++){
for (int j = j & j--){
if(((Comparable) dest[j - 1]).compareTo(dest[j]) & 0){
swap(dest, j-1, j);
//归并相邻两个列表并保存在dest中
private static void Merge(Object[] src, Object[] dest, int low, int mid,
int high) {
int p = //第一个列表指针
//第二个列表指针
while(p & mid && q &high){
if(((Comparable) src[p]).compareTo(src[q]) &= 0){
dest[i++] = src[p++];
dest[i++] = src[q++];
//添加剩余的值
while(p & mid && i&high){
dest[i++] = src[p++];
while(q & high && i&high){
dest[i++] = src[q++];
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
浏览 10380
zhouYunan2010
浏览: 171533 次
来自: 湖南
博主 方便加一个QQ么 有个问题想请教您 qq：2691669 ...
吖龙Sam 写道博主，请问在ValueAnimator.add ...
博主，请问在ValueAnimator.addUpdateLi ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)算法：归并算法的递归与非递归形式
归并算法是将两个或两个以上的有序表组合成一个新的有序表，它的原理是：假设初始序列含有n个记录，则可以看成是n个有序子序列，两两归并，得到[n/2]个有序子序列，再次归并……不断重复直至归并到长度为n的有序序列，这样的排序方法称为2路归并排序。
实例一：递归形式的2路归并算法
#define MAXSIZE 4
int data[MAXSIZE] = {2,1,0,3};
* 功能：将from数组min到max-1下标数据排好序，最后的结果是to[min]...to[max-1]
* 输入：1.待排序的数组；2.排好序的数组；3.相关位置设定
* 输出：无
void merge(int from[],int to[],int min,int m,int max)
/*将from[]数组两侧元素排序放在to[]上，直至一侧"溢出"*/
int i = min , j = m+1;
while(min<=m && j<=max)
if(from[min] < from[j])
to[i++] = from[min++];
to[i++] = from[j++];
/*由于子序列已经排好序，当上面的循环结束时，将还没"溢出"的一侧剩余元素直接赋给后面的to[]*/
if(min <= m)
for(int k =0; k<=m- k++)
to[i+k] = from[min+k];
if(j <= max)
for(int k = 0; k <= max-j; k++)
to[i+k] = from[j+k];
* 功能：不断分组归并
* 输入：1.待排序的数组；2.排好序的数组；3.相关位置设定
* 输出：无
void mSort(int from[],int to[],int min,int max)
if(min == max)
// 不断分组，直至拷贝了一份原数组
to[min] = from[max];
int m = (min+max)/2;
int temp[MAXSIZE];
// 创建一个新的数组来存储排序的子序列
mSort(from,temp,min,m);
// 此时中间下标变为最大下标 , temp数组递归后为下一层的要megre的to数组
mSort(from,temp,m+1,max);
// 此时中间下标+1变为最小下标
merge(temp,to,min,m,max);
// 分到不能再分就开始不断归并
void print(int *data)
for(int i = 0; i < MAXSIZE; i++)
printf("%d ",data[i]);
printf("\n");
void main(int argc, char* argv[])
print(data);
mSort(data,data,0,MAXSIZE-1);
print(data);
}打印结果：
由程序可以看出，每分组一次就要创建一个临时存放数据的数组，这无疑会降低性能，所以可以采用非递归形式的归并算法。vcD4KPHA+PGJyPgo8L3A+CjxwPsq1wP22/qO6t8e13bnp0M7KvbXEMsK3uemyosvjt6g8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:">#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 8
int data[MAXSIZE] = {5,2,1,7,6,4,0,3};
* 功能：归并排序，自下而上，不采取递归方式，而是通过算法自下而上
* 输入：待排序数组，数组元素个数
* 输出：无
void merge_sort(int *list, int length)
int i, left_min, left_max, right_min, right_max,
int *tmp = (int*)malloc(sizeof(int) * length);
// 由此至终都是和这个动态分配的数组打交道
for (i = 1; i < i *= 2)
// 当i = 1时代表要归并的序列大小为1，依次类推
/*当前大小的序列需要归并的次数，通过改变left_min来移动*/
for (left_min = 0; left_min
right_max =
/*将两组序列排序进入tmp直至一段"溢出"，尤其注意right_min的移动*/
while (left_min < left_max && right_min
list[right_min] ? list[right_min++] : list[left_min++];
/*如果溢出的是右端，待排序的数组读取左端后面较大的数据*/
while (left_min
list[--right_min] = tmp[--next];
free(tmp);
void main()
print(data);
merge_sort(data,MAXSIZE);
print(data);
打印结果基本同上
归并排序很重要的一个思想是，在归并的子序列是已经排好序的，这也是其中算法的关键。归并排序的时间复杂度是O(nlogn)，处理大量数据时性能远比简单排序算法要好，其中非递归归并算法的空间复杂度比递归归并算法的要小，整体性能较好。}