归并排序

归并排序2012-03-08 blogjava nijiaben下面简单的说说归并排序，所谓归并排序就是说把输入数组分成两组当然也可以大于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（）;}}