1、二分检索：
1 package divideAndConquer; 2 3 public class BINSRCH { 4 int j=-1; 5 BINSRCH(){ 6 int[] a={4,7,3,1,5,6,0,8,9,2}; 7 binsrch(a,10,5);//binsrch(a,10,5,j),这样不可以，java传给参数的只是引用，函数改变参数参数，在外面看不到变化 8 System.out.println(j); 9 } 10 public void binsrch(int[] A,int n,int x){ 11 int low,high,mid; 12 low=0; 13 high=n-1; 14 while(low<=high){ 15 mid=(low+high)/2; 16 if(A[mid]==x){ 17 j=mid; 18 return; 19 } 20 else{ 21 if(A[mid]<x){ 22 low=mid+1; 23 }else{ 24 high=mid-1; 25 } 26 } 27 } 28 } 29 public static void main(String[] args) { 30 // TODO Auto-generated method stub 31 new BINSRCH(); 32 } 33 34 }
2、分治法对数组a={2,4,67,8,98,44,2,344,43,3,4,4,3,4,3}排序（非降）
1 package divideAndConquer; 2 3 import java.lang.reflect.Array; 4 5 public class MERGE { 6 int[] a={2,4,67,8,98,44,2,344,43,3,4,4,3,4,3}; 7 int n=Array.getLength(a); 8 MERGE(){ 9 danc(0,n-1); 10 //selectSort(0,n-1); 11 System.out.print("分治法排序结果："); 12 for(int i=0;i<n;i++){ 13 System.out.print(a[i]+" "); 14 } 15 } 16 public void danc(int low,int high){ 17 int mid=(low+high)/2; 18 if(high-low<5){ 19 selectSort(low,high); 20 return; 21 } 22 danc(low,mid); 23 danc(mid+1,high); 24 merge(low,mid,high); 25 26 } 27 public void selectSort(int low,int high){ 28 int temp; 29 for(int i=low+1;i<=high;i++){ 30 temp=a[i]; 31 int j=i; 32 while(temp<a[j-1]&&j>low){//这里一定要加上 j>low 防止越界 33 a[j]=a[j-1]; 34 j--; 35 } 36 a[j]=temp; 37 } 38 } 39 public void merge(int low,int mid,int high){ 40 int[] b=new int[high-low+1]; 41 int i=low; 42 int j=mid+1; 43 int k=0; 44 while(i<=mid&&j<=high){ 45 if(a[i]<=a[j]){ 46 b[k]=a[i]; 47 i++; 48 k++; 49 }else{ 50 b[k]=a[j]; 51 j++; 52 k++; 53 } 54 } 55 if(i<=mid){ 56 for(;i<=mid;i++){ 57 b[k]=a[i]; 58 k++; 59 } 60 }else 61 for(;j<=high;j++){ 62 b[k]=a[j]; 63 k++; 64 } 65 for(i=0;i<high-low+1;i++){ 66 a[low+i]=b[i]; 67 } 68 } 69 public static void main(String[] args) { 70 // TODO Auto-generated method stub 71 new MERGE(); 72 } 73 74 }
调试代码：
1 package divideAndConquer; 2 3 import java.lang.reflect.Array; 4 5 public class MERGE { 6 int[] a={2,4,67,8,98,44,2,344,43,3,4,4,3,4,3}; 7 int n=Array.getLength(a); 8 MERGE(){ 9 System.out.println(n); 10 danc(0,n-1); 11 //selectSort(0,n-1); 12 System.out.print("分治法排序结果："); 13 for(int i=0;i<n;i++){ 14 System.out.print(a[i]+" "); 15 } 16 } 17 public void danc(int low,int high){ 18 int mid=(low+high)/2; 19 if(high-low<5){ 20 selectSort(low,high); 21 return; 22 } 23 System.out.print("划分子集 成:"); 24 for(int i=low;i<=high;i++){ 25 if(i==mid+1) 26 System.out.print(" "); 27 System.out.print(a[i]+" "); 28 } 29 System.out.println(); 30 danc(low,mid); 31 danc(mid+1,high); 32 merge(low,mid,high); 33 34 } 35 public void selectSort(int low,int high){ 36 System.out.println("选择排序处理："+low+"-到-"+high+"号元素"); 37 for(int i=0;i<n;i++){ 38 39 System.out.print(a[i]+".."); 40 } 41 System.out.println(); 42 int temp; 43 for(int i=low+1;i<=high;i++){ 44 temp=a[i]; 45 int j=i; 46 while(temp<a[j-1]&&j>low){//这里一定要加上 j>low 防止越界 47 a[j]=a[j-1]; 48 j--; 49 } 50 a[j]=temp; 51 } 52 for( int i=low;i<=high;i++){ 53 54 System.out.print(a[i]+"*"); 55 } 56 System.out.println(); 57 } 58 public void merge(int low,int mid,int high){ 59 System.out.println("合并："+low+"+"+mid+"+"+high); 60 int[] b=new int[high-low+1]; 61 int i=low; 62 int j=mid+1; 63 int k=0; 64 while(i<=mid&&j<=high){ 65 if(a[i]<=a[j]){ 66 b[k]=a[i]; 67 i++; 68 k++; 69 }else{ 70 b[k]=a[j]; 71 j++; 72 k++; 73 } 74 } 75 if(i<=mid){ 76 for(;i<=mid;i++){ 77 b[k]=a[i]; 78 k++; 79 } 80 }else 81 for(;j<=high;j++){ 82 b[k]=a[j]; 83 k++; 84 } 85 for(i=0;i<high-low+1;i++){ 86 a[low+i]=b[i]; 87 } 88 for( i=low;i<=high;i++){ 89 90 System.out.print(a[i]+" "); 91 } 92 System.out.println(); 93 System.out.print("此时整个a数组状态:"); 94 for( i=0;i<n;i++){ 95 96 System.out.print(a[i]+".."); 97 } 98 System.out.println(); 99 } 100 public static void main(String[] args) { 101 // TODO Auto-generated method stub 102 new MERGE(); 103 } 104 105 }
