分治思想--小测试(归并排序后续)
1 package cn.it; 2 3 import java.util.Arrays; 4 // 利用分治思想 实现 归并排序 5 public class Fz { 6 public static void main(String[] args) { 7 int a[]={1,2,3,4,5,6,8,7,3,4,9,0}; 8 int temp[] = new int[a.length]; 9 sortdiv(a, 0, a.length-1, temp); 10 System.out.println(Arrays.toString(a)); 11 } 12 13 private static void sortdiv(int[] a,int start,int end,int[] temp){ 14 if(start<end){ 15 //后序遍历 递归左子树 递归右子树 跟 16 int mid=(start+end)/2; 17 sortdiv(a, start, mid,temp); 18 sortdiv(a, mid+1, end,temp); 19 merge(a, start, end, mid,temp); 20 } 21 } 22 23 private static void merge(int[] a,int start,int end,int mid,int[] temp){ 24 int i=start; 25 int j=mid+1; 26 int k=0; 27 28 //将较少者存入临时空间 29 while(i<=mid && j<=end){ 30 if(a[i]<a[j]){ 31 temp[k++]=a[i++]; 32 }else{ 33 temp[k++]=a[j++]; 34 } 35 } 36 37 //剩余的加入队尾 38 while(i<=mid){ 39 temp[k++]=a[i++]; 40 } 41 42 while(j<=end){ 43 temp[k++]=a[j++]; 44 } 45 46 //将有序临时数组置换回实际存储的数组 47 for(int l=0;l<k;l++){ 48 a[start+l]=temp[l]; 49 } 50 51 } 52 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。