排序算法笔记:归并排序 MergeSort
博客专区 > CheN_exe 的博客 > 博客详情
排序算法笔记:归并排序 MergeSort
CheN_exe 发表于4年前
排序算法笔记:归并排序 MergeSort
  • 发表于 4年前
  • 阅读 46
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

/**
 * 归并排序
 * 简述:稳定算法
 * 		用递归的方式平分数组,直至只有一个元素为止.然后分别将两个数组进行排序并合并,直至数组完全合并为止.
 * 时间复杂度:
 * 		Θ(nlgn)
 * 空间复杂度:
 * 		O(n)
 * 递归式:
 * 		T(n) = if n=1 Θ(1)
 *        	   if n>1 2T(n/2)+Θ(n) 
 * 优点:
 * 		
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 * 
 */
public class MergeSort {

	/**
	 * 正序int[]
	 * 
	 * @param int[]
	 */
	public static int[] asc( int[] array ) {
		return divide( array );
	}
	
	/**
	 * 分化
	 * @param array
	 * @return
	 */
	private static int[] divide( int[] array ) {
		if( array.length > 1 ){
			int[] leftArray = divide( Arrays.copyOfRange( array , 0, array.length/2 ));
			int[] rightArray = divide( Arrays.copyOfRange( array , array.length/2 , array.length ));
			return combine( leftArray , rightArray );
		}else{
			return array;
		}
	}
	
	/**
	 * 合并
	 * @param leftArray
	 * @param rightArray
	 * @return
	 */
	private static int[] combine( int[] leftArray, int[] rightArray ){
		int array[] = new int[leftArray.length + rightArray.length];
		int leftIndex = 0, rightIndex = 0;
		while( leftIndex + rightIndex < array.length ){
			if( leftIndex == leftArray.length ){
				array[ leftIndex + rightIndex ] = rightArray[rightIndex];
				rightIndex++;
			}else if( rightIndex == rightArray.length || leftArray[leftIndex] <= rightArray[rightIndex] ){
				array[ leftIndex + rightIndex ] = leftArray[leftIndex];
				leftIndex++;
			}else{
				array[ leftIndex + rightIndex ] = rightArray[rightIndex];
				rightIndex++;
			}
		}
		return array;
	}
}

 

若有错误或不妥之处,敬请谅解并指点。

共有 人打赏支持
粉丝 3
博文 31
码字总数 16641
×
CheN_exe
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: