当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

2012/3/27----归并排序

发表于: 2012-03-27   作者:akon405   来源:转载   浏览次数:
摘要: 通过使用分治算法的思想来对数组进行排序(这里叫做归并排序),分治算法的核心思想就是把一个问题分解n个小问题,然后把这n个小问题分别解决,最后再把这n个小问题的结果合并便可以得到结果了。(分解--解决--合并)/* * 分治算法对数组的排序的java实现(归并排序) * version 1.0 2012/3/27 * @author akon */ package com.akon

通过使用分治算法的思想来对数组进行排序(这里叫做归并排序),分治算法的核心思想就是把一个问题分解n个小问题,然后把这n个小问题分别解决,最后再把这n个小问题的结果合并便可以得到结果了。(分解--解决--合并)/*

 * 分治算法对数组的排序的java实现(归并排序)
 * version 1.0 2012/3/27
 * @author akon
 */
package com.akon405.www;

public class MergeSort {
	public void merge(int[] A,int left,int mid,int right){
		int n1=mid-left+1;//第一个数组的长度
		int n2=right-mid;//第二个数组的长度
		int i,j,k;
		int[] R=new int[100];
		int[] L=new int[100];
		for(i=1;i<=n1;i++){
			L[i]=A[left+i-1];
		}
		for(j=1;j<=n2;j++){
			R[j]=A[mid+j];
		}
		L[n1+1]=99999;
		R[n2+1]=99999;
		i=1;
		j=1;
		for(k=left;k<right;k++){
			if(L[i]<=R[j]){
				A[k]=L[i];
				i++;
			}else{
				A[k]=R[j];
				j++;
			}
		}
	}
	
	public void merge_Sort(int[] A,int left,int right){
		if(left<right){
			int mid;
			mid=(left+right)/2;
			Merge_Sort(A,left,mid);
			Merge_Sort(A,mid+1,right);
			Merge(A,left,mid,right);
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		mergeSort a=new mergeSort();
		int[] A={2,12,32,43,13,45,1,8,23,47,89,90};
		int left=0;
		int right=A.length-1;
		a.merge_Sort(A, left, right);
		for(int i=0;i<A.length;i++)
			System.out.println(A[i]);
	}

}
 

 

2012/3/27----归并排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1, 复杂度:O (n log n) 2路归并排序的基本思想:n个记录,看作n个有序子序列,每个子序列的长度为
《算法导论》2.3-7很值得一练。其中用到了归并排序、二分查找等等: Give a Q(n lg n) time algorit
<img src="http://img.it610.com/image/product/cf7
普通的归并排序,如果不了解可以参考本博客:http://blog.csdn.net/lsjseu/article/details/9771203
归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and
归并排序是分治算法的一个典型的体现: 将原问题分解为若干的子问题进行求解就可以了。 分治算法的步
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
1 归并排序(MergeSort) 归并排序最差运行时间是O(nlogn),它是利用递归设计程序的典型例子。 归并
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号