归并是将两个或多个存序记录序列合并成一个有序序列。归并方法有多种,一次对两个有序记录序列进行归并,称为路归并排序,也有三路归并排序及多路归并排序。本实例是二路归并排序,基本方法如下:
(1) 将 n 个记录看成是 n 个长度为 1 的有序子表。
(2) 将两两相邻时有序无表进行归并。
(3) 重复执行步骤 (2) 直到归并成一个长度为 n 的有序表。
源码
package com; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s=new Scanner (System.in); int n=s.nextInt(); int [] a=new int [n]; int [] temp=new int [n]; for(int i=0;i<n;i++) a[i]=(int)(Math.random()*100); mergesort(a,0,a.length-1,temp); System.out.println(Arrays.toString(a)); } public static void mergesort (int[] a,int left,int right,int[] temp) { if(left<right) { int mid=(left+right)/2; mergesort(a,left,mid,temp); mergesort(a,mid+1,right,temp); merge(a,left,mid,right,temp); } } public static void merge(int[] a,int left,int mid,int right,int[] temp) { int i=left; int j=mid+1; int t=0; while(i<=mid&&j<=right) { if(a[i]<=a[j]) { temp[t]=a[i]; t++; i++; }else { temp[t]=a[j]; t++; j++; } } while(i<=mid) { temp[t]=a[i]; t++; i++; } while(j<=right) { temp[t]=a[j]; t++; j++; } t=0; int templeft=left; while(templeft<=right) { a[templeft]=temp[t]; t++; templeft++; } } }
以上代码仅供参考