java 算法之归并排序详解及实现代码
java算法之归并排序详解
一、思想
归并排序：将一个数组排序，可以先（递归地）将它分成两半部份分别排序，然后将结果归并起来；
二、概念
归并：将两个有序的数组归并成一个更大的有序数组；
三、特点
优点：能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比；
缺点：需要额外的空间和N成正比；
四、实现方法
将两个不同的有序数组归并到第三个数组中；
先将前半部分排序，在将后半部分排序，然后在数组中移动元素而不需要使用额外的空间；
五、代码
/**
*归并排序
*
*@authorpengcx
*
*/
publicclassMergeextendsSort{
/**归并所需的辅助数组*/
privatestaticComparable[]aux;
publicstaticvoidmain(String[]args){
String[]a={"d","a","w","b","q"};
Merge.sort(a);
show(a);
}
publicstaticvoidsort(Comparable[]a){
aux=newComparable[a.length];
sort(a,0,a.length-1);
}
/**
*排序数组的a[lo]至a[hi]元素
*
*@parama
*数组a
*@paramlo
*最小元素位置lo
*@paramhi
*最大元素位置hi
*/
privatestaticvoidsort(Comparable[]a,intlo,inthi){
if(hi<=lo){
return;
}
//计算数组中间位置
intmid=lo+(hi-lo)/2;
//排序数组a左边的元素
sort(a,lo,mid);
//排序数组a右边的元素
sort(a,mid+1,hi);
//合并数组a左边和右边的元素
merge(a,lo,mid,hi);
}
/**
*将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并
*
*@parama
*合并的数组a
*@paramlo
*最小数组元素lo
*@parammid
*中间元素位置mid
*@paramhi
*最大元素位置hi
*/
publicstaticvoidmerge(Comparable[]a,intlo,intmid,inthi){
inti=lo,j=mid+1;
for(intk=lo;k<=hi;k++){
aux[k]=a[k];
}
for(intk=lo;k<=hi;k++){
//如果左边的元素用尽，取右边的元素
if(i>mid){
a[k]=aux[j++];
}
//如果右边的元素用尽，取左边的元素
elseif(j>hi){
a[k]=aux[i++];
}
//如果右半边的当前元素小于左半边的当前元素，取右半边元素
elseif(less(aux[j],aux[i])){
a[k]=aux[j++];
}
//如果右半边的当前元素大于等于左半边的当前元素，取左半边元素
else{
a[k]=aux[i++];
}
}
}
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！