算法导论--合并算法

    技术2022-11-22  43

    import java.util.Arrays; public class Merge_sort{ public static void merge(int[]a,int p,int q,int r){ int n1=q-p+1; int n2=r-q; int[] L=new int[n1]; for(int l=0;l<n1;l++) L[l]=a[l+p]; int[] R=new int[n2]; for(int l=0;l<n2;l++) R[l]=a[l+q+1]; int i=0; int j=0; for(int k=p;k<r+1;k++){ if(i==n1){ while(j<n2){ a[k]=R[j]; j++; k++; } return; } if(j==n2){ while(i<n1){ a[k]=L[i]; i++; k++; } return; } if(L[i]<=R[j]){ a[k]=L[i]; i++; }else{ a[k]=R[j]; j++; } } } public static void merge_sort(int[]a,int p,int r){ if(p<r){ int q=(p+r)/2; merge_sort(a,p,q); merge_sort(a,q+1,r); merge(a,p,q,r); } } public static void main(String[] args){ int[] a = { 11, 55, 23, 78, 21, 90, 15, 88 }; merge_sort(a,0,5); System.out.println(Arrays.toString(a)); } }

    最新回复(0)