归并排序的分析与Java实现-白红宇

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。

归并排序算法依赖归并操作。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序在众多排序算法中既是稳定排序，效率也比较高，同时，归并排序不仅可以用于内排序，还可以用于外排序。

1.两个有序数列的合并

设两个有序数列放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量 R1中，待合并完成后将 R1 复制回 R[low..high]中。

（1）合并过程

合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。

合并时依次比较 R[i]和 R[j]的关键字，取关键字较小的记录复制到 R1[p]中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。

重复这一过程直至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记录依次复制到 R1 中即可。

（2）动态申请 R1

实现时，R1 是动态申请的，因为申请的空间可能很大，所以在工程上应用时，可能需要加入申请空间是否成功的处理。

2.归并排序的实现

（1）二路归并的思路

将数组划均分为两个子数组；

对两个字数组进行排序；

将排序好的两个字数组归并。

所谓 N路归并是指将数组均分为N个子数组，将字数组排序后再归并。二路归并是归并排序的最一般的情况。

（2）归并排序实现的一般化过程

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针到达序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

（3）实现过程

                            
public
class
MergeSort { 
    
    
public
static
void
main(String[] args){ 
        
int
[] arr=
new
int
[]{ 
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
};
        
for
(
int
i=
0
;i<arr.length;i++){ 
            
System.out.print(arr[i]+
","
);          
        
}
        
//想起引用传递和值传递的问题，数组是引用传递，不需要什么返回值
        
sort(arr,arr.length);
        
System.out.println(
"排序后"
); 
        
for
(
int
i=
0
;i<arr.length;i++){ 
            
System.out.print(arr[i]+
","
);          
        
}
    
}
    
    
public
static
void
sort(
int
[] arr,
int
n){ 
        
if
(arr==
null
|| n<
2
){ 
            
return
;
//边界情况
        
}
        
divide(arr,
0
,n-
1
);
    
}
    
/**
     
*
     
* @param arr 待排序数组
     
* @param left 待排序区间左侧下标
     
* @param right 待排序区间右侧下标
     
*/
    
public
static
void
divide(
int
[] arr,
int
left,
int
right){ 
        
        
if
(left>=right){ 
            
return
;
        
}
        
int
m=(left+right)/
2
;
//从中间开始分成两个区间进行归并
        
divide(arr,left,m);
//一直递归划分直到区间长度为1
        
divide(arr,m+
1
,right);
        
//开始逐级往上进行归并操作
        
binaryMerge(arr,left,m,right);
//第一次进行merge操作的递归栈最深层此时是merge(arr,0,0,1)
    
}
    
    
/**
     
* 对数组arr[left...right]位置进行递归的归并排序
     
* @param arr
     
* @param left
     
* @param rigtht
     
* @param temp
     
*/
    
public
static
void
binaryMerge(
int
[] arr,
int
left,
int
m,
int
right){ 
        
/**
         
* 归并排序的时间复杂度为O(n),指的就是最大长度为n的临时数组
         
*/
        
int
[] temp=
new
int
[right-left+
1
];
        
int
l=left;
//
        
int
r=m+
1
;
//
        
int
index=
0
;
//
        
        
while
(l<=m && r<=right){ 
            
if
(arr[l]<arr[r]){ 
                
temp[index]=arr[l];
                
index++;
                
l++;
            
}
else
{ 
                
temp[index]=arr[r];
                
index++;
                
r++;
            
}
        
}
        
        
/**
         
* 交换完了如果哪一侧数组还有剩余，则全部赋值
         
* 实际的一次归并下面的两个while循环只会执行一个
         
* warn!不要漏了等于的情况！否则会每两个元素丢失一个元素
         
*/
        
while
(l<=m){ 
            
temp[index]=arr[l];
            
index++;
            
l++;
        
}
        
        
while
(r<=right){ 
            
temp[index]=arr[r];
            
index++;
            
r++;
        
}
        
        
/**
         
* 用临时数组的部分排序的序列全部替换待排序数组中对应的部分
         
* 这里应该用temp.length，不能用arr.length
         
*/
        
for
(
int
i=
0
;i<temp.length;i++){ 
            
//注意是left，此时的l是已经变化了的
            
arr[left+i]=temp[i];
        
}
        
    
}
    
}
         
       

（4）时间和空间复杂度

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，

比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

3.空间复杂度为O(1)的归并排序

归并排序的空间复杂度为O(N)，

通过优化可以把空间复杂度降为O(1)，通过手摇算法，

但实际上通过手摇算法后，此时的时间复杂度会上升。

4.多路归并排序

归并排序的思想可以用于外排序。

外排序是相对内排序而言的，在常规的小规模排序过程中，都是直接在内存中对数据进行排序处理的，而对于数据量极大的排序问题，这种方式是不现实的。

这个时候就要通过外排序来进行，先将数据划分成多个规模能在内存中处理的子集，对各个子集排序后存放在临时的磁盘文件上，然后再将这些子集归并到输出文件中。

这个过程要使用到多路归并。

本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/3421123.html，如需转载请自行联系原作者