[数据结构与算法]Java学习日记day6(今天写个算法)

今天的任务为：大整数乘法 和合并排序算法
算法设计与分析第二章重点之分治法
思想就是将大问题分解为小问题，小问题合并这样子
递归的将大整数分为两个小整数，分解到只剩一位时按传统方式计算

算术表达式为上

package muyahan;
import java.lang.Math;
import java.util.Arrays;
import java.util.Scanner;
public class test{
public static int sign(int x){
   if(x>0){
   return 1
   }
   else if(x<0){
   return -1;
   }
   else{
   return 0;
   }
   public static int jisuan(int x,int y,int n){
      int x=abs(x);
      int y=abs(y);
      if(x==0||y==0){
      return 0 ;
      }else if(n==1){
      return sign*x*y;
      }else{
        int A = (int) x / pow(10, (int)(n / 2));//A是大整数前半部分的数
        int B = x - A * pow(10, n / 2);
        int C = (int) y / pow(10, (int)(n / 2));
        int D = y - C * pow(10, n / 2);
        int AC = jisuan(A, C, n / 2);
        int BD = jisuan(B, D, n / 2);
        int ABDC = jisuan((A - B), (D - C), n / 2) + AC + BD;
        return sign * (AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD); //降维处理
          }
       }
       

public static void main(String[]args){
int x,y,n;
Scanner a=new Scanner(Systrm.in);
int x=a.nextInt();
int y=a.nextInt();
int n=a.nextInt();
System.out.println(jisuan(x,y,n);
}
}
**第一次用java写长算法可能有点错误，等ipad来了好好写...**

注意JAVA导包建立类，主类，方法，导包后建立对象使用等等细节，我将在日后的多次运用中逐渐养成好的思维习惯
合并排序 -----即归并排序上学期数据结构见到过
小问题合并
两个有序子数组合并为一个有序数组段
采用递归分解
非递归方式分解

public class MergeSort {
static int a[]={0,10,20,6,9,35,38,78,54,32,15,28,79,30,51}
static int b[]=new[15];
public static void main()String[] args){
mergesort(1,14)//除了0排序后面的数组元素
for(int i=1;i<=14;i++)
System.out.print(a[i]+" ");
}
public static void mergesort(int left,int right){
if(left<right){
int mid=(left+right)/2;
mergesort(left,mid);
mergesort(mid+1,right);
merge(left,mid,right);
copy(a,b,left,right);//用b数组辅助处理，递归一次复制一次//看的头疼明天看。。。。。。。。