算法7.自然合并排序与最长公共子序列。

柔光的暖阳◎ 2022-07-13 08:24 52阅读 0赞

1.  如果数组中部分元素已按自然数顺序排放，例如，数组  
    ![这里写图片描述][SouthEast]

，则初期自然排好序的子数组段显然有4段，分别为  
![这里写图片描述][SouthEast 1]  
，  
![这里写图片描述][SouthEast 2]  
，  
![这里写图片描述][SouthEast 3]  
和  
![这里写图片描述][SouthEast 4]  
。请充分利用上述特点设计并实现一个自然合并排序算法。  
(1) 算法设计思路  
先对数组进行一次线性扫描，记录下部分有序数组的断开位置和个数，个数用于判断最后一个断开的位置是否为数组末尾，位置用于合并数组。循环-依次将相邻的两两数组进行合并，直到最后剩下一个数组，即为合并排序好的数组。

(2) 算法实现的伪代码  
功能描述：对数组进行线性扫描，记录下该断点的位置和断点个数  
输入：数组大小n  
输出：数组划分后的断点个数+1

int fenduan(int n)
        int j=0;
        rem[j++]=0
        for i=0 to n-2
        if (arr[i]>arr[i+1]) rem[j]=i;j++;//记录断点的位置
        end for 
        rem[j++]=n-1;
        return j;

功能描述:通过记录的断点位置将两两相邻的伪数组进行合并排序
    输入：起始位置a，断点位置m，终点位置r
    输出：

void merge(int a,int m,int r)
        int i=a,j=m+1,k=a;
        while (i<=m&&j<=r)
        if (arr[i]<=arr[j]) newarr[k++]=arr[i++]
        else newarr[k++]=arr[j++];
        end while
        if (i>m)
        for (int q=j to r) newarr[k++]=arr[q] end for 
        else for (int q=I to m) newarr[k++]=arr[q] end for

功能描述:循环活动最终的自然合并排序
    输入：数组的大小n
    输出：

sort(int num)
        int a=huafen(num)
        while (a!=2)
        for (int i=0 to a-1)
        if (i==0)
        merge(rem[i] ,rem[i+1], rem[i+2]);
        else if (i+2>a-1)
        merge(rem[i+1],rem[i+1],rem[i+1])
        else merge(rem[i]+1,rem[i+1],rem[i+2])
        end for
        /将合并好的数组复制到原数组
        for (int j=0;j<n;j++)
        arr[j]=newarr[j];end for 
        a=huafen(n);//继续获得断点个数+1

(3) 实现代码

import java.util.Scanner;
        public class main {
            static int[] arr;//创建录入数据用的数组
            static int[] newarr;//用于存储合并后的数组
            static int[] rem;//记录数组断点的位置
            static int n;//数组的大小
    
            //自然合并主方法
            static void sort(int num){
                int a=huafen(num);//断点的个数+1
                while (a!=2){
       //如果只有一个断点，则证明已经排好顺序
                    int i=0;            
                    for (i=0;i<a-1;i+=2){
                        if (i==0)//对第一队有序数组进行排序
                            merge(rem[i] ,rem[i+1], rem[i+2]);
                        else if (i+2>a-1)//剩余的部分有序数组无法两两匹配
                            merge(rem[i+1],rem[i+1] , rem[i+1]);
                        else 
                            merge(rem[i]+1, rem[i+1], rem[i+2]);
    
        // else if (i+2>a-1&&i+1==a-1)//最后两个有序数组两两合并
        // merge(rem[i], rem[i], rem[i+1]);
        // else//有序数组两两合并
        // merge(rem[i] ,rem[i+1], rem[i+2]);
                    }
                    //将合并好的数组复制到原数组
                    for (int j=0;j<n;j++)
                        arr[j]=newarr[j];
                    a=huafen(n);//继续获得断点个数+1
                }
            }
    
            //划分数组的有序部分，并且记录下该断点的位置和断点个数
            private static int huafen(int n) {
                int num=0;
                rem[num++]=0;
                for (int i=0;i<n-1;i++){
                    if (arr[i]>arr[i+1])
                        rem[num++]=i;
                }
                rem[num++]=n-1;//将最后一个断点位置赋值为数组最后一个位置，便于排序
                return num;
            }   
    
            //进行合并排序
            private static void merge(int a, int m, int r) {
                int i=a;
                int j=m+1;
                int k=a;
                while (i<=m&&j<=r){
                    if (arr[i]<=arr[j])
                        newarr[k++]=arr[i++];
                    else {
                        newarr[k++]=arr[j++];
                    }
                }
                    if (i>m)
                        for (int q=j;q<=r;q++)
                            newarr[k++]=arr[q];
                    else {
                        for (int q=i;q<=m;q++)
                            newarr[k++]=arr[q];
                    }
            }
    
            public static void main(String []args){
                Scanner in=new Scanner(System.in);
                System.out.println("输入数组的大小");
                n=in.nextInt();
                //初始化数据
                newarr = new int[n];
                arr=new int[n];
                rem=new int[n+1];
    
                System.out.println("录入数据，数据用空格格开");
                String line=in.nextLine();
                line=in.nextLine();
                String arrg[]=line.split(" ");
                for (int j=0;j<arrg.length;j++)
                    arr[j]=Integer.parseInt(arrg[j]);   
                sort(n);
                System.out.println("自然合并排序后");
                for (int i=0;i<n;i++)
                    System.out.print(newarr[i]+" ");
            }
        }

(4) 算法运行结果及计算时间复杂度分析  
![这里写图片描述][SouthEast 5]

![这里写图片描述][SouthEast 6]  
![这里写图片描述][SouthEast 7]

时间复杂度为O(n)

(5) 体会  
自然合并排序算法比一般合并排序算法多了一个扫描的方法。通过扫描后记录断点的位置和断点的个数，可以很清晰的使用合并算法来合并两个相邻的有序数组断。在每次的合并后，继续扫描一次，然后再合并，直到扫描到只有一个断点个数。在编写代码的过程中，老是在循环递归合并算法卡住了，不能很好的判断要合并的相邻的两个数组断的起点，断开的位置，和终点位置，导致耗费了比较多的时间

1.  最长公共子序列LCS问题：给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定X = \{x1, x2, …, xm\}和Y = \{y1, y2, …, yn\}，请找出X和Y的最长公共子序列。例如：  
    输入：X = ABCHFGASJKXBD Y = DBDHASXB  
    输出：LCS = BHASXB  
    (1) 算法设计思路  
    创建二维数组c存储X和Y的最长公共子序列的长度，二维数组b记录c的值是由哪一个子问题解得到的，然后构造最长公共子序列。

(2) 算法实现的伪代码  
功能描述：创建备忘录，记录最长子序列的长度和对应所在位置  
输入：字符串x，y和其长度n，m。备忘录c，b  
输出：备忘录c，b

void max(int n,int m ,char[] x,char[] y,int[][] c,int[][] b)
        for(int I to n) c[i][0]=0
        for (int j to m) c[0][j]=0;
        for (int i to n)
        for (int j to m)
        if (x[i]=y[j])  c[i][j]=c[i-1][j-1]+1;b[i][j]=1;
        else if (c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];b[i][j]=2; 
        else c[i][j]=c[i][j-1];b[i][j]=3;
        end for 
        end for

功能描述：使用备忘录输出共同的子序列
    输入：字符串x和x的长度，y的长度。备忘录b
    输出：最长公共子序列

if (i==0||j==0)return;
            if (b[i][j]==1) input(i-1, j-1,x,b); 输出(x[i]);
            else if (b[i][j]==2)input(i-1, j,x,b);
            else input(i, j-1,x,b);

(3) 实现代码

package 算法分析;
    
        import java.util.Scanner;
    
        public class main {
            //创建备忘录，记录所有的数据
            static void max(int n,int m,char[] x,char[] y,int[][] c,int[][] b){
                //初始化数组
                for (int i=1;i<=n;i++)
                    c[i][0]=0;
                for (int j=1;j<=m;j++)
                    c[0][j]=0;
            /* * c[i][j]=① 0 ,i=0,j=0 * ②c[i]-1[j-1]+1 , Xi=Yj * ③max{ (c[i][j-1],c[i-1][j]) } , Xi!=Yi */
                for (int i=1;i<=n;i++)
                    for (int j=1;j<=m;j++){
                        if (x[i]==y[j]){
                            c[i][j]=c[i-1][j-1]+1;
                            b[i][j]=1;
                        }
                        else if (c[i-1][j]>=c[i][j-1]){
                            c[i][j]=c[i-1][j];
                            b[i][j]=2;
                        }
                        else {
                            c[i][j]=c[i][j-1];
                            b[i][j]=3;
                        }
                    }
            }
    
            //使用备忘录
            static void input(int i,int j,char[] x,int[][] b){
                if (i==0||j==0)
                    return;
                if (b[i][j]==1){
       //如果Xi=Yj,递归，输出该值
                    input(i-1, j-1,x,b);
                    System.out.print(x[i]);
                }
                else if (b[i][j]==2){
                    input(i-1, j,x,b);
                }
                else 
                    input(i, j-1,x,b);
            }
    
            public static void main(String []args){
                Scanner in=new Scanner(System.in);
                System.out.println("输入字符串x[]");
                String line=in.nextLine();
                char[] x;
                x=line.toCharArray();
                int n=x.length;//获取字符串x的长度
                //为x头加上空格
                char c1[]=null;
                c1=x;
                x=new char[n+1];
                x[0]=' ';
                for (int i=1;i<=n;i++)
                    x[i]=c1[i-1];
                System.out.println("输入字符串Y[]");
                String line2=in.nextLine();
                char[] y;
                y=line2.toCharArray();
                int m=y.length;//获取字符串y的长度
                //为字符串y头加上空格
                char c2[]=null;
                c2=y;
                y=new char[m+1];
                y[0]=' ';
                for (int i=1;i<=m;i++)
                    y[i]=c2[i-1];
    
                int[][] c=new int[n+1][m+1];
                int[][] b=new int[n+1][m+1];
    
                max(n, m, x, y, c, b);
                input(n, m, x, b);
            }
        }

(4) 算法运行结果及计算时间复杂度分析  
![这里写图片描述][SouthEast 8]

![这里写图片描述][SouthEast 9]

![这里写图片描述][SouthEast 10]  
O(mn)+O(n+m)  
(5) 体会  
重在理解。备忘录的使用非常的巧妙，经常会忘记使用备忘录而导致结果错误。使用动态规划的时候，先找出最优解的性质，并刻画其结构特征，然后递归定义最优解，再自底而上的方式计算最优值，最后根据计算最优值时得到的信息，构造最优解。分析最优解的性质很重要，也比较有难度。通过做这道题，发现我现在对动态规划的理解还差得远呢，但是只要肯努力，就没有什么不可能。

[SouthEast]: /images/20220713/a8fb4f15da014c8d9f7ee2ea5d42ee21.png
[SouthEast 1]: /images/20220713/0593b4e67c2845ca9fd1bcee66da52f9.png
[SouthEast 2]: /images/20220713/6a9b73094d984c4d862a3aa0981bb6a8.png
[SouthEast 3]: /images/20220713/4e128b4547dc413584684d13fc76455b.png
[SouthEast 4]: /images/20220713/8c93235a386343eb964ead7832c40abe.png
[SouthEast 5]: /images/20220713/18980c90ff5e4bdf9c61d066ef49ad07.png
[SouthEast 6]: /images/20220713/9eb44099e2d844a3948e24346a48a0d0.png
[SouthEast 7]: /images/20220713/b13a27dee7614a0e88f10d868bd44b06.png
[SouthEast 8]: /images/20220713/0330907fec9541229c69c628cb6ab287.png
[SouthEast 9]: /images/20220713/5cbe510ec2b543ca951d31b24fc00894.png
[SouthEast 10]: /images/20220713/228ef8897ebf423f8cce87608274f22a.png