Merge Sort 的 最差排序时间为 n log n,不错的一个排序算法
merge sort
看了一下算法导论，写了一个小程序。有如果要排序int,可以封装为Integer或者自己重新写一个类似程序
package org.winnerbao.alg.sort;
/**
* 合并排序算法
*/
public class MergeSort
{
/**
* 输入对象一个数组，输出按照从小到大顺序的数组
* 要求 输入数组需实现Comparable接口
*/
public void sort(Comparable[] objs)
{
//0
if(objs == null)
throw new IllegalArgumentException("bad params : null ");
//1 检查输入数组各个实例，是否实现了Comparable接口
boolean b = checkForCopr(objs);
if(!b)
throw new IllegalArgumentException("bad params : the input all the objects in the array objs should implements Comparable interface ");
//3 调用2分法 合并排序，返回排序结果
dichotomy_sort(objs,0,objs.length-1);
}
/**
* 对objs数组的第begin-end进行二分法合并排序
* begin : 0,1,...,objs.length-1
* end : 0,1,...,objs.length-1
* end >= begin
* 这是一个私有方法，所以默认所有参数都是合法的。调用者必须先保证输入参数的正确性
*/
private void dichotomy_sort(Comparable[] objs,int begin,int end)
{
if (objs.length == 1)
return ; //一个对象，不用排序了
//分到最后了，就一个元素
if(begin == end )
return;
//将objs的 begin到end分为两部分分别进行二分法合并排序
dichotomy_sort(objs, begin , begin+ (int)(Math.floor((end-begin)/2.0)) );
dichotomy_sort(objs, begin+ (int)Math.floor((end-begin)/2.0)+1, end );
//将得到的两个有序部分进行合并
merge(objs , begin,begin+ (int)Math.floor((end-begin)/2.0),begin+ (int)(Math.floor((end-begin)/2.0))+1,end );
}
/**
* objs的 b1~e1 有序， b2~e2有序
* 而且 b1<=e1<b2<=e2, e1=b2+1
* 这里面合并的时候使用了一个临时数组，增加了对内存的使用和计算时间
* 最好找到更好的办法
*/
private void merge(Comparable[] objs,int b1 ,int e1 , int b2,int e2)
{
Comparable[] nObjs = new Comparable[e2-b1+1];
int i=b1 ,j=b2,k=0;
for(; i<e1+1 && j<e2+1 ; k++)
{
if(objs[i].compareTo( objs[j]) < 0)
{
nObjs[k]=objs[i];
i++;
}else
{
nObjs[k]=objs[j];
j++;
}
}//end for
//可能有一端比较长，没有合并完，追加上
if(i != e1+1)
{
for( ; i<e1+1 ; i++)
nObjs[k++]=objs[i];
}
if(j != e2+1)
{
for( ; j<e2+1 ; j++)
nObjs[k++]=objs[j];
}
//将nObjs的值，替换到objs中
for(k=0; k<nObjs.length; k++)
{
objs[b1+k]=nObjs[k];
}
}//end merge
/**
* 检查输入数组各个实例，是否实现了Comparable接口
* 如果没有实现，返回false
*
*/
private boolean checkForCopr(Object[] objs)
{
return true;
}
public static void main(String[] args)
{
//准备测试数据
Integer n0 = new Integer(7);
Integer n1 = new Integer(4);
Integer n2 = new Integer(8);
Integer n3 = new Integer(3);
Integer n4 = new Integer(19);
Integer n5 = new Integer(6);
Comparable[] c = new Comparable[6];
c[0] = n0;
c[1] = n1;
c[2] = n2;
c[3] = n3;
c[4] = n4;
c[5] = n5;
//排序前输出测试数据
System.out.print(" before sort : ");
for(int i=0;i<c.length;i++)
{
System.out.print(((Integer)c[i]).intValue());
System.out.print(" , ");
}
//排序
new MergeSort().sort(c);
//输出排序后的测试数据
System.out.println("");
System.out.print(" after sort : ");
for(int i=0;i<c.length;i++)
{
System.out.print(((Integer)c[i]).intValue());
System.out.print(" , ");
}
System.out.println("");
}//end main
}