本文最先发布于本人个人博客
http://www.lovestblog.cn
下面简单的说说归并排序，所谓归并排序就是说把输入数组分成两组当然也可以大于2组，一般我们是等量的分成2组，通过递归我们可以把长度为n的数组分成n个数组，我们通过一定的关键字比较把两两结合成一个有序的数组，然后回溯到原数组大小的有序数组，具体的我就不多说了，因为比较简单，到网上可以找些相关文章看看什么是归并排序，归并排序算法可以再O(nlogn)的时间内对长度为n的序列完成排序，至于合并两个有序数组，假如这两个数组的长度分别为m和n，那么我们只需要O(n+m)的时间久可以完成对这两个有序数组的合并，下面还是代码说明之：
package org.rjb.Sort;
/** *//**
* 归并排序（升序排列）
* @author ljp
*
*/
public class MergeSort 
{
/** *//**
* 对原始数组进行平等划分为两个子数组
* @param nums
*/
public static void sort(int[] nums){
int n=nums.length;
if(n<=1)
return;
int nums1[]=new int[n/2];
int nums2[]=new int[n-n/2];
for(int i=0,j=nums1.length;j<nums.length;i++,j++){
if(i<nums1.length){
nums1[i]=nums[i];
}
nums2[i]=nums[j];
}
//递归对子数组进行划分
sort(nums1);
sort(nums2);
//把子数组排序后的结果进行合并
merge(nums,nums1,nums2);
}
/** *//**
* 合并两个有序的子数组为一个有序的数组
* @param nums 合并之后的数组
* @param num1 有序的子数组
* @param num2 有序的子数组
*/
public static void merge(int[] nums,int num1[],int num2[]){
int n1=num1.length-1;
int n2=num2.length-1;
int k=0;
int k1=0,k2=0;
while(k1<=n1||k2<=n2){
int e=0;
if(k1>n1){//如果第一个数组已经全部比较完了，那么我们只要直接复制第二个数组的条目到合并数组中即可
e=num2[k2++];
}else if(k2>n2){//如果第二个数组已经全部比较完了，那么我们只要直接复制第一个数组的条目到合并数组中即可
e=num1[k1++];
}else if(num1[k1]>num2[k2]){//把比较的两个条目中关键值小的放到合并数组中
e=num2[k2++];
}else{
e=num1[k1++];
}
nums[k++]=e;
}
}
/** *//**
* 主函数
* @param args
*/
public static void main(String args[]){
int[] nums={10,2,3,7,4,9,1};
sort(nums);
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]+" ");
}System.out.println();
}
}
posted on 2009-05-29 16:55
你假笨 阅读(1215)
评论(0) 编辑 收藏