最近笔者在阅读 算法 一书 ,重温经典数据结 构和算法，毕竟一直以来的说法是程序就是数据结构＋算法。而我想要聊聊的是归并算法的优化. 归并算法所需的时间和 NlgN 成正比，效率还是挺高的，所以可以用归并算法处理数百万甚至更大规模的数据， 但是归并算法也是存在不足之处的，需要额外的空间来完成排序，而且空间和N的大小也是 成正比的
优化
算法一书中有提到可以通过一些细致的修改实现在一定幅度缩短归并排序的运行时间， 完整代码地址
优化1 -- 对小规模子数组使用插入排序
因为归并算法使用的递归在处理小规模问题时会导致小规模问题中的方法被频繁调用， 所以改进对它们的处理方法就能改进整个算法。对于排序即将完成时候的未排序小数组 可以通过使用插入排序或者选择排序来避免递归调用。
未改进归并排序
public static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
if(hi<=lo){
return;
}
int mid=lo+(hi-lo)/2;
sort(a,aux,lo,mid);/*将左半边排序*/
sort(a,aux,mid+1,hi);/*将右半边排序*/
merge(a,aux,lo,mid,hi);
}
改进后归并排序
public static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
if(hi<=lo){
return;
}else if(hi-lo<15){
insertionSort(a,lo,hi);
return;
}
else {
int mid = lo + (hi - lo) / 2;
sort(a,aux, lo, mid);
sort(a,aux, mid + 1, hi);
merge(a,aux, lo, mid, hi);
}
}
轨迹图如下：(图来源于 算法 一书)
算法一书中提到：使用插入排序处理小规模的子数组(比如长度小于15) 一般可以将归并排序的 运行时间缩短10%-15%.实践出真知，还是要自己来测试一下更佳。
测试1
对100*1000 个字符进行排序，结果如下：
测试2
对1000*1000 个字符进行排序，结果如下：
测试3
对10000*1000 个字符进行排序，结果如下
测试4
对100000*1000 个字符进行排序，结果如下
测试5
对500000*1000 个字符进行排序，结果如下
小结
由于篇幅问题，笔者无法将所有的测试结果都展示出来，但是从上面的结果，可以看出 对于小数组，使用插入排序的确对性能有一定幅度提高(最开始的测试可能因为数据量 太小所以结果误差较大，但是这并不妨碍得出一个比较接近的结果)
优化2 -- 测试数组是否已经有序
可以添加一个判断条件，如果 a[mid]小于等于 a[mid+1], 便可认为数组已经有序并跳过
merge 方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时
间都变成线性的了
未改进归并排序
public static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
if(hi<=lo){
return;
}
int mid=lo+(hi-lo)/2;
sort(a,aux,lo,mid);/*将左半边排序*/
sort(a,aux,mid+1,hi);/*将右半边排序*/
merge(a,aux,lo,mid,hi);
}
改进后归并排序
public static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
if(hi<=lo){
return;
}else if(hi-lo<15){
insertionSort(a,lo,hi);
return;
}
else {
int mid = lo + (hi - lo) / 2;
sort(a,aux, lo, mid);
sort(a,aux, mid + 1, hi);
if(less(a[mid+1],a[mid])){
merge(a,aux,lo,mid, hi);
}
}
}
测试1
对100*1000 个字符进行排序，结果如下：
测试2
对1000*1000 个字符进行排序，结果如下：
测试3
对10000*1000 个字符进行排序，结果如下：
测试4
对100000*1000 个字符进行排序，结果如下：
测试5
对500000*1000 个字符进行排序，结果如下：
小结
从上面的结果可以看出，只是添加了一个判断数组是否已经有序的条件，算法性能就优化了 大概20%左右, 不得不说真的令人惊讶。
注意: 运行结果跟操作系统，电脑配置，以及运行次数都相关