本文最先发布于本人个人博客[url]http://www.lovestblog.cn[/url]
下面简单的说说归并排序，所谓归并排序就是说把输入数组分成两组当然也可以大于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(); }}
相关资源：归并排序 C语言实现
