归并排序java实现
日期： 2017-06-05 分类： 跨站数据测试 306次阅读
归并排序
归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。来源于【百度百科】。
解读：归并排序可以简单理解为两个步骤
1、递归二分待排序序列，最终映射成一颗二叉树，二叉树的叶子节点为单个待排序元素。
2、合并有序序列，每一次合并，将产生一个有序序列。合并的原则是，从树的底层，兄弟节点进行合并。重点理解【归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。来源于百度百科。】
举例说明：
待排序序列 1,5,6,2,3,7,4
递归排序的拆分与合并实例图
(1,5,6,2,3,7,4) 根节点 第0层
/ \
/ \
/ \
(1,5,6,2) (3,7,4) 第1层
/ \ / \
/ \ / \
(1,5) (6,2) 3 (7, 4) 第2层
/\ /\ / \
/ \ / \ / \
1 5 6 2 7 4 第3层
那是如何进行合并的呢？从叶子节点所在层开始进行合并（兄弟节点之间的合并）
第3层 (1,5) (2,6) (4,7)
第2层 (1,2,5,6) (3,4,7)
第1层 (1,2,3,4,5,6,7)
上述就是归并排序的核心所在，通常我们使用递归来实现，运用递归的核心：1、重复工作；2：递归结束条件（很重要），比如归并排序的递归结束（退出）条件为待分元素只包含一个元素（本例中的startInx == endInx）,源码所在地址：https://git.oschina.net/zhcsoft/StudyDemo.git,所在类路径：persistent.prestige.console.algorithm.MergeSort。
现给出源码：
package persistent.prestige.console.algorithm;
/**
* 归并排序
* @author dingwei2
*
*/
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
testMergeSort();
// int[] a = new int[] {2,5,16,21,1,4,7,10,22 };
// int[] tmp = new int[a.length];
// merge(a,0,4,8, tmp);
// testMerge();
}
/**
* 测试案例
*/
public static void testMergeSort() {
int[] a = new int[] {1,8,7,16,4,9,15,12};
testMergeSort(a);
int[] b = new int[] {1};
testMergeSort(b);
int[] c = new int[] {1,7,9,5,6,7,9};
testMergeSort(c);
}
private static void testMergeSort(int[] a) {
System.out.println("待排序序列:");
for(int i : a) {
System.out.print(i + " ");
}
System.out.println("");
int[] tmp = new int[a.length];
mergeSort(a, 0, a.length -1, tmp);
System.out.println("排序后的序列:");
for(int i : a) {
System.out.print(i + " ");
}
System.out.println("");
}
/**
* 归并排序,
*/
public static final void mergeSort(int[] source, int startInx, int endInx, int[] tmp) {
if( startInx != endInx ) { // startInx == endInx,说明不可再分
// mid 所在的元素放在下半区 [startInx, mid) [mid,endInx]
int mid = ((endInx - startInx ) >> 1) + 1 + startInx;
mergeSort(source, startInx, mid - 1, tmp); // 将左边部分继续拆分 mid 所在元素放下半区 [startInx, mid)
mergeSort(source, mid, endInx, tmp); // 将右边部分继续拆分 mid 所在元素放下半区 [mid,endInx]
merge(source, startInx, mid, endInx, tmp);
//为什么是放在这里呢？就是归并排序的第一阶段，就是拆分元成一个有序序列（包含单个元素）。分解后的的元素，其实可以看出如下图
/*
* 待排序序列 1,5,6,2,3,7,4
* 递归排序的拆分与合并实例图
* (1,5,6,2,3,7,4) 根节点 第0层
* / \
* / \
* / \
* (1,5,6,2) (3,7,4) 第1层
* / \ / \
* / \ / \
* (1,5) (6,2) 3 (7, 4) 第2层
* /\ /\ / \
* / \ / \ / \
* 1 5 6 2 7 4 第3层
* 那是如何进行合并的呢？从叶子节点所在层开始进行合并（合并孩子）
* 第3层 (1,5) (2,6) (4,7)
* 第2层 (1,2,5,6) (3,4,7)
* 第1层 (1,2,3,4,5,6,7)
*
*
*
*
*/
} // 如果不可分，则跳出递归（递归的出口在这里）(startInx == endInx)
}
/**
* 归并排序的合并部分（合并两个有序序列）
* @param a
* @param stInx 开始合并下标
* @param midInx 中间位置
* @param endInx 结束下标
* @param tmp 临时空间，等于带排序长度，在一次归并排序中，共用一个临时空间。
*
*/
public static final void merge(int[] a, int stInx, int midInx, int endInx, int[] tmp) {
int alen = midInx > stInx ? midInx - stInx : 0;
int blen = endInx - midInx + 1;
int len = alen + blen;
int aIndex = stInx;
int bIndex = midInx;
alen += stInx; //
blen += midInx; // 这里主要是为了 aIndex < alen && bIndex < blen 服务的
int al = 0;
while( al < len ) {
if(aIndex < alen && bIndex < blen) {
if(a[ aIndex ] >= a[bIndex]) {
tmp[al] = a[bIndex];
bIndex ++;
} else {
tmp[al] = a[aIndex];
aIndex ++;
}
} else if(aIndex < alen) {
tmp[al] = a[aIndex];
aIndex ++;
} else {
tmp[al] = a[bIndex];
bIndex ++;
}
al++;
}
System.arraycopy(tmp, 0, a, stInx, len); // 将tmp拷贝到source数组，该部门元素的排序
}
/**
* 先实现 合并算法,然后转换为 merge 方法的实现
*
* 该方法为草稿类，主要合并两个已排序序列算法，进而演变为 merge(int[] a, int stInx, int midInx, int endInx, int[] tmp)
*
*/
public static final void testMerge() {
int[] a = new int[]{ 1,4,7,10,22};
int[] b = new int[] {2,5,16,21};
int len = a.length + b.length;
int[] c = new int[len];
int aIndex = 0;
int bIndex = 0;
int al = 0;
while( al < len ) {
if(aIndex < a.length && bIndex < b.length) {
if(a[ aIndex ] >= b[bIndex]) {
c[al] = b[bIndex];
bIndex ++;
} else {
c[al] = a[aIndex];
aIndex ++;
}
} else if(aIndex < a.length) {
c[al] = a[aIndex];
aIndex ++;
} else {
c[al] = b[bIndex];
bIndex ++;
}
al++;
}
for(int i : c ) {
System.err.print(i + " ");
}
}
}
归并排序算法复杂度分析 n * logn
对于一个包含n个元素的待排序序列，首先需要将排序序列分解成一颗二叉树，运算次数为 logn(2的对数)
然后合并操作，每一层进行归并运算的时候，需要比较元素的次数为n
所以算法复杂度为 n * logn
归并排序需要一个临时空间，所需要的空间为元序列的两倍。
欢迎加笔者微信号(dingwpmz)，加群探讨，笔者优质专栏目录：
上一篇： Java从.CSV文件中读取数据和写入
下一篇： 快速排序算法java版实现
精华推荐