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++]; } } } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!